#2478. 「九省联考 2018」林克卡特树

内存限制:1024 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小 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

输出格式

输出一行一个整数,表示答案。

样例

样例输入 1

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

样例输出 1

14

样例解释 1

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

样例 2

见附加文件中的 lct/lct2.inlct/lct2.ans

数据范围与提示

对于 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

提示:题目并不难。