CF1004E Sonya and Ice Cream

Sonya 非常喜欢冰淇淋。即使在编程比赛期间，她也会吃冰淇淋。因此，她决定要开设属于自己的冰淇淋店。 Sonya 住在一个有 $n$ 个路口和 $n-1$ 条街道的城市。所有街道都是双向的，并连接两个路口。可以通过一条或多条街道从任意一个路口到达另一个路口。市政厅只允许在路口开设商店，不能在街道中间开店。 Sonya 有恰好 $k$ 个值得信任的朋友。如果她开设一家商店，必须由她的一个朋友在那里工作，防止有人不付钱就吃冰淇淋。由于 Sonya 不想错过重要的比赛，她本人不会在商店工作。 Sonya 希望她所有的冰淇淋店都位于一条长度为 $r$（$1 \le r \le k$）的简单路径上，即位于不同的路口 $f_1, f_2, \dots, f_r$，并且对于每个 $i$ 从 $1$ 到 $r-1$，$f_i$ 和 $f_{i+1}$ 之间有一条街道相连。 Sonya 也很关心潜在的顾客，因此她还希望最小化所有路口到最近冰淇淋店的最大距离。两个路口 $a$ 和 $b$ 之间的距离等于从 $a$ 到 $b$ 需要经过的所有街道长度之和。因此，Sonya 希望最小化 $$ \max_{a} \min_{1 \le i \le r} d_{a,f_i} $$ 其中 $a$ 取所有 $n$ 个路口的值，$f_i$ 表示第 $i$ 家 Sonya 的商店所在的路口，$d_{x,y}$ 表示路口 $x$ 和 $y$ 之间的距离。 Sonya 不确定自己能否找到最优的商店位置，因此她请求你帮她选择不超过 $k$ 家商店，使它们位于一条简单路径上，并且所有路口到最近商店的最大距离最小。

第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 10^5$），分别表示路口数量和朋友数量。 接下来的 $n-1$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $d_i$（$1 \leq u_i, v_i \leq n$，$v_i \neq u_i$，$1 \leq d \leq 10^4$），表示一条连接路口 $u_i$ 和 $v_i$ 的街道及其长度。保证每对路口之间至多有一条街道，并且任意两个路口之间都可以互相到达。

输出一个整数，表示所有路口到最近冰淇淋店的最小可能最大距离。Sonya 的商店必须位于一条简单路径上，且商店数量不超过 $k$。

在第一个样例中，你可以选择路径 2-4，因此答案为 4。 第一个样例。 在第二个样例中，你可以选择路径 4-1-2，因此答案为 7。 第二个样例。 由 ChatGPT 4.1 翻译