AT_xmascon16_h.High-powered Illuminations

为了庆祝圣诞节，兔子准备了一棵圣诞树。

细心的参赛者可能已经发现，这里所说的圣诞树实际上是指图论中的一种树结构。这棵树由 $N$ 个顶点组成（编号为 $1, 2, \ldots, N$），并且由 $N-1$ 条边连接。这里，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$，长度为 $C_i$（$1 \leq i \leq N-1$）。

兔子手头有 $K$ 个灯泡，计划将这些灯泡装饰在树的不同顶点上。然而，由于这些灯泡的光线非常刺眼，兔子希望能够尽可能地将灯泡之间的距离拉开，让整棵树看起来不那么刺目。这里所谓的灯泡之间的距离，指的是灯泡所在顶点之间的路径长度。两个顶点之间的距离，是指从一个顶点到另一个顶点的路径上，所有边长之和的最小值。

现在，兔子希望在 $N$ 个顶点中选择 $K$ 个顶点来放置灯泡，请你帮助计算灯泡之间的最小距离 $d$ 的最大可能值。

输入从标准输入给出，格式如下：

$N$ $K$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\cdots$ $A_{N-1}$ $B_{N-1}$ $C_{N-1}$

输出一个整数，表示灯泡之间最短距离 $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$ 分。

示例说明 1

可以将灯泡放置在顶点 $1, 3, 4$ 上。

示例说明 2

可以将灯泡放置在顶点 $2, 4, 6, 9$ 上。

本翻译由 AI 自动生成