2932. 林克卡特树

【题目描述】

小 L 最近沉迷于塞尔达传说：荒野之息（TheLegendofZelda: BreathofTheWild） 无法自拔，他尤其喜欢游戏中的迷你挑战。

游戏中有一个叫做 “LCT” 的挑战，它的规则是这样子的：现在有一个 N 个点的 树（Tree），每条边有一个整数边权 vi ，若 vi ≥0，表示走这条边会获得 vi 的收益；若 vi < 0 ，则表示走这条边需要支付 −vi 的过路费。小 L 需要控制主角 Link 切掉（Cut） 树上的 . 恰 . 好 K 条边，然后再连接 K 条边权为 0 的边，得到一棵新的树。接着，他会选 择树上的两个点 p,q ，并沿着树上连接这两点的简单路径从 p 走到 q，并为经过的每 条边支付过路费 / 获取相应收益。

海拉鲁大陆之神 TemporaryDO 想考验一下 Link。他告诉 Link，如果 Link 能切掉合适的边、选择合适的路径从而使 总收益 - 总过路费 最大化的话，就把传说中的大师之剑送给他。

小 L 想得到大师之剑，于是他找到了你来帮忙，请你告诉他，Link 能得到的 总收益 - 总过路费 最大是多少。

【输入格式】

从文件 lct.in 中读入数据。 输入第一行包含两个正整数 N,K，保证 0≤ K < N ≤3×105。 接下来 N−1 行，每行包含三个整数 xi,yi,vi，表示第 i 条边连接图中的 xi,yi 两点， 它的边权为 vi。

【输出格式】

输出到文件 lct.out 中。 输出一行一个整数，表示答案。

【样例输入】

5 1
1 2 3
2 3 5
2 4 -3
4 5 6

【样例输出】

14

【样例 1 解释】

一种可能的最优方案为：切掉 (2,4,−3) 这条边，连接 (3,4,0) 这条边，选择 (p,q) = (1,5)。

【子任务】

• 对于 10% 的数据，k = 0 ;

• 对于另外 10% 的数据，k = 1 ;

• 对于另外 15% 的数据，k = 2 ;

• 对于另外 25% 的数据，k≤100 ;

• 对于其他数据，没有特殊约定。

对于全部的测试数据，保证有 1≤ N ≤3×105,1≤ xi,yi ≤ N,|vi|≤106 。

【提示】

题目并不难。

【来源】

2018八省联考