← 返回题目列表

AtCoder · xmascon16_h

H. 高功率照明

中文机器翻译题面 查看原题

配点 : 100 点

問題文

兔子为圣诞节准备了圣诞树。

明智的参与者可能已经注意到,圣诞树指的当然是图论中的树结构。树由 N 个顶点(顶点 1,\ 2,\ ...,\ N)组成,N-1 条边组成。i (1 \leq i \leq N-1第[[T000009]] 条边是顶点 A_i 与 边缘 B_i 领带长度 C_i 的边。

兔子是 它有一个矩形网格 K 个电球,每个电球都想放在树的顶点上进行装饰。然而,由于兔子拥有的电球光量非常大,如果电球彼此太近,树会显得太刺眼。因此,兔子决定尽量把电球之间的距离拉远来布置电球。这里,电球之间的距离是指电球安装的顶点之间的距离。2 个顶点间的距离,是从一个顶点到另一个顶点沿树的边走时,所经过的边长度之和的最小值。

N 个顶点中 K 个放置电球并点亮时,电球之间距离的最小值 d .d 的值的最大值。 保证

制約

  • 2 \leq K \leq N \leq 200,000.
  • 1 \leq A_i, B_i \leq N.
  • 1 \leq C_i \leq 5,000.
  • A_i \neq B_i.
  • 输入表示的是树结构。 如果针对

部分点

  • N \leq 40,000 这样的数据集回答正确,50 点。 如果所有满足
  • 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 输出(小于 50 点。 如果所有满足

入力

输入是按以下格式从标准输入给出的。

N K
A_1 B_1 C_1
A_2 B_2 C_2
:
A_{N-1} B_{N-1} C_{N-1}

出力

灯泡之间距离的最小值 d 可以考虑的最大值 1 行输出。 没有


入力例 1

4 3
2 1 100
3 2 200
4 2 300

出力例 1

300

頂点 1,\ 3,\ 4 上标示即可。


入力例 2

9 4
1 2 1
1 3 1
3 4 1
1 5 1
6 5 1
7 5 1
8 5 1
9 8 1

出力例 2

3

頂点 2,\ 4,\ 6,\ 9 上标示即可。


入力例 3

6 2
1 2 20
1 3 16
1 4 1224
4 5 1400
4 6 1700

出力例 3

3100

入力例 4

12 4
4 8 1214
12 7 890
3 1 651
5 9 1990
1 2 1671
4 1 55
6 4 761
7 2 862
11 10 1469
11 7 1122
12 9 364

出力例 4

2940