配点 : 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