34593번 - 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 integer $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 ≤ n ≤ 2 \times 10^5$
• $0 ≤ k ≤ n$
• $1 ≤ u_i , v_i ≤ n$
• $1 ≤ l_i ≤ 10^9$
• It is guaranteed that the input roads form a tree.