小 L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。
游戏中有一个叫做 “LCT” 的挑战,它的规则是这样子的:现在有一个 个点的树(Tree),每条边有一个整数边权 ,若 ,表示走这条边会获得 的收益;若 ,则表示走这条边需要支付 的过路费。小 L 需要控制主角 Link 切掉(Cut)树上的恰好 条边,然后再连接 条边权为 边,得到一棵新的树。接着,他会选择树上的两个点 ,并沿着树上连接这两点的简单路径从 走到 ,并为经过的每条边支付过路费 / 获取相应收益。
海拉鲁大陆之神 TemporaryDO 想考验一下 Link。他告诉 Link,如果 Link 能切掉合适的边、选择合适的路径从而使总收益-总过路费最大化的话,就把传说中的大师之剑送给他。
小 L 想得到大师之剑,于是他找到了你来帮忙,请你告诉他,Link 能得到的总收益-总过路费最大是多少。