4485: 「九省联考 2018」林克卡特树
内存限制：1024 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
小 L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。
游戏中有一个叫做 “LCT” 的挑战，它的规则是这样子的：现在有一个 $N$ 个点的树（Tree），每条边有一个整数边权 $v_i$ ，若 $v_i \ge 0$，表示走这条边会获得 $v_i$ 的收益；若 $v_i \lt 0$ ，则表示走这条边需要支付 $−v_i$ 的过路费。小 L 需要控制主角 Link 切掉（Cut）树上的**恰好** $K$ 条边，然后再连接 $K$ 条边权为 $0$ 边，得到一棵新的树。接着，他会选择树上的两个点 $p, q$ ，并沿着树上连接这两点的简单路径从 $p$ 走到 $q$ ，并为经过的每条边支付过路费 / 获取相应收益。
海拉鲁大陆之神 TemporaryDO 想考验一下 Link。他告诉 Link，如果 Link 能切掉合适的边、选择合适的路径从而使**总收益-总过路费**最大化的话，就把传说中的大师之剑送给他。
小 L 想得到大师之剑，于是他找到了你来帮忙，请你告诉他，Link 能得到的**总收益-总过路费**最大是多少。
输入
输入第一行包含两个正整数 $N, K$，保证 $0 \le K \lt N \le 3 \times 10^5$。
接下来 $N − 1$ 行，每行包含三个整数 $x_i, y_i, v_i$，表示第 $i$ 条边连接图中的 $x_i, y_i$ 两点，它的边权为 $v_i$。
输出
输出一行一个整数，表示答案。
样例输入 复制
5 1
1 2 3
2 3 5
2 4 -3
4 5 6样例输出 复制
14提示
数据范围：对于 $10\%$ 的数据，$k = 0$ ; 对于另外 $10\%$ 的数据，$k = 1$ ; 对于另外 $15\%$ 的数据，$k = 2$ ; 对于另外 $25\%$ 的数据，$k \le 100$ ; 对于其他数据，没有特殊约定。 对于全部的测试数据，保证有 $1 \le N \le 3 × 10^5$, $1 \le x_i, y_i \le N$, $|v_i| \le 10^6$ 。 提示：题目并不难。