P15902 [TOPC 2025] Gas Station

Alex is planning rest area placements on a simplified model of Taiwan’s freeway system. The system contains $n$ interchanges, connected by $n - 1$ bidirectional roads. The network is connected, and there is exactly one shortest route between any pair of interchanges. The $i$-th road connects interchanges $u_i$ and $v_i$, and has a length of $l_i$. Exactly $k$ rest areas with gas stations can be built, each located at an interchange. A driver may start a trip from any interchange and travel to any other, always following the unique shortest path. They begin each trip with a full tank of gas and can refuel only at interchanges that have a rest area. Alex is curious about the smallest possible fuel tank capacity $d$ such that it’s possible to place the $k$ rest areas in a way that ensures no driver will ever run out of gas. On any trip, the driver must never have to travel more than $d$ units along the path without passing through a rest area, including at the beginning or end of the journey. The goal is to figure out the minimum such $d$, assuming the rest areas are placed in the best possible way.

The first line contains two integers $n, k$. Followed by $n - 1$ lines, the $i$-th of which contains three integers $u_i, v_i, l_i$, representing the $i$-th road connects interchanges $u_i$ and $v_i$ with a length $l_i$.

Output one integer, the smallest possible fuel tank capacity $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$ - It is guaranteed that the input roads form a tree.