感谢您帮助海蒂!现在已经是四月二号了,她却又被珍妮召唤了。恶作剧似乎还没有结束……
与此同时,海蒂决定不再信任她的朋友。无论如何,也不算太多。她的相对缺乏信任表现在:以前她不会被要求去拜访同一个人两次,但现在她只能确定她不会被要求多次拜访同一个人。 k 次。 (对于珍妮来说,这包括她一开始的第一次访问。简单版本中的情况对应于设置 k = 1.)
这并不像看起来那么糟糕,因为两个朋友之间的一张路线票可以让海蒂在这对朋友之间旅行一整天(双向)。换句话说,一旦她支付了一对朋友之间的旅行费用,该对朋友之间的所有进一步旅行都是免费的。
在最坏的情况下,海蒂现在会浪费多少钱?
输入
第一行包含两个空格分隔的整数 - 好友数量 n (
)和参数 k (1 ≤ k ≤ 105)。下一个 n - 1 行每行包含三个空格分隔的整数 u, v 和 c (0 ≤ u, v ≤ n - 1, 1 ≤ c ≤ 104)意味着 u 和 v 是朋友并且往返的费用 u 和 v is c.
再次保证输入的社交网络形成一棵树。
输出
再次输出一个整数——门票成本的最大总和。
示例
输入复制
9 3
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
输出复制
15
输入复制
9 5
0 1 1
0 2 1
1 3 2
1 4 2
1 5 2
2 6 3
2 7 3
2 8 3
输出复制
17
输入复制
11 6
1 0 7932
2 1 1952
3 2 2227
4 0 9112
5 4 6067
6 0 6786
7 6 3883
8 4 7137
9 1 2796
10 5 6200
输出复制
54092
注意
在第一个示例中,Heidi 最坏的情况是按以下顺序拜访朋友: 0, 1, 5, 1, 3, 1, 0, 2, 6, 2, 7, 2, 8。观察没有朋友的访问次数超过 3 次。