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.

노트