[八省联考 2018] 林克卡特树

题目描述

小 L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。 游戏中有一个叫做 LCT 的挑战,它的规则是这样子的:现在有一个 $N$ 个点的树,每条边有一个整数边权 $v_i$,若 $v_i \geq 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$。 接下来 $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

说明

### 样例解释 一种可能的最优方案为:切掉 $(2, 4, -3)$ 这条边,连接 $(3, 4, 0)$ 这条边,选择 $(p, q) = (1, 5)$。 ### 数据范围 - 对于 $10\%$ 的数据,$k = 0$; - 对于另外 $10\%$ 的数据,$k = 1$; - 对于另外 $15\%$ 的数据,$k = 2$; - 对于另外 $25\%$ 的数据,$k \leq 100$; - 对于其他数据,没有特殊约定。 对于全部的测试数据,保证 $1 \leq N \leq 3 \times 10^5$,$0 \leq K \leq 3 \times 10^5$,$K \lt N$,$1 \leq x_i,y_i \leq N$,$|v_i| \leq 10^6$。 ### 提示 题目并不难。