P15902 [TOPC 2025] Gas Station

亚历克斯正在台湾高速公路系统的简化模型上规划休息区的布置。该系统包含 $n$ 个立交桥，由 $n-1$ 条双向道路连接。该网络是连通的，且任意两个立交桥之间有且仅有一条最短路径。第 $i$ 条道路连接立交桥 $u_i$ 和 $v_i$，长度为 $l_i$。 可以建造恰好 $k$ 个带有加油站的休息区，每个休息区位于一个立交桥处。驾驶员可以从任意一个立交桥出发，前往任意另一个立交桥，始终沿着唯一的最短路径行驶。他们每次行程开始时油箱是满的，并且只能在设有休息区的立交桥处加油。 亚历克斯想知道最小的燃油箱容量 $d$，使得存在一种放置 $k$ 个休息区的方式，确保任何驾驶员都不会耗尽燃油。在任何行程中，驾驶员在任意两个休息区之间（包括行程起点和终点）行驶的距离不得超过 $d$ 个单位，即不得连续行驶超过 $d$ 距离而不经过休息区。目标是求出在最优放置休息区的情况下，这样的最小 $d$ 值。

第一行包含两个整数 $n$ 和 $k$。 接下来的 $n-1$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $l_i$，表示第 $i$ 条道路连接立交桥 $u_i$ 和 $v_i$，长度为 $l_i$。

输出一个整数，表示最小的燃油箱容量 $d$。

- $2 \le n \le 2 \times 10^5$ - $0 \le k \le n$ - $1 \le u_i, v_i \le n$ - $1 \le l_i \le 10^9$ - 保证输入的道路构成一棵树。 翻译由 DeepSeek V3.2 完成