시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)110221222.222%

문제

Seoul City Mayor Hanbyeol plans to build a subway system to alleviate traffic congestion on its jam-packed roads. However, due to budget constraints, only a maximum of $K$ stations can be built, and a single path of roads must connect all the stations.

Specifically, when the layout of Seoul can be represented as a connected graph with $N$ nodes and $N-1$ bidirectional edges, where a node represents a building and an edge represents a road, Hanbyeol must select a simple path of $X$ nodes, where $1 \le X \le K$, and build stations on every node along that path.

Hanbyeol wants to minimize the maximum distance between the buildings to the nearest station. To help Hanbyeol, write a program that determines the best location for the subway stations so that such value is minimized.

입력

The first line of input contains two space-separated integers: $N$, denoting the count of the nodes in the city, and $K$, denoting the count of the maximum subway stations that Hanbyeol can build. ($1 \le K \le N \le 300\,000$)

The $i$-th of the next $N-1$ lines of input contains three space-separated integers: $u_i$ and $v_i$, denoting the indices of nodes that the $i$-th road is connecting, and $l_i$, denoting the length of the $i$-th road in kilometers. ($1 \le u_i, v_i \le N;$ $1 \le l_i \le 10^{12};$ $i \ne j \rightarrow \{u_i,v_i\} \ne \{u_j,v_j\}$)

출력

Output the maximum distance from any building to the nearest subway station when it is the minimum possible, in kilometers.

서브태스크 1 (3점)

Modified constraints apply: $1 \le K \le 4;$ $1 \le N \le 40$.

서브태스크 2 (8점)

Modified constraints apply: $K=1;$ $1 \le N \le 300\,000$.

A ‘subway system’ with just one station? That's insane!

서브태스크 3 (25점)

Modified constraints apply: $1 \le K \le N \le 2\,000$.

서브태스크 4 (64점)

Original constraints apply: $1 \le K \le N \le 300\,000$.

예제 입력 1

9 3
1 2 5
2 3 8
3 4 6
3 5 9
5 6 8
5 9 11
6 7 1
6 8 12

예제 출력 1

13


 

예제 입력 2

9 5
1 2 5
2 3 8
3 4 6
3 5 9
5 6 8
5 9 11
6 7 1
6 8 12

예제 출력 2

11

This test corresponds to the Subtask 3.

노트

(For Sogang students:) Note that this problem is an improvised version that matches the format of a problem in a general programming contest. While in the exam, the original scoring was:

  • $55$ points for Subtask 1.
  • $40$ points for Subtask 2.
  • $3$ points for Subtask 3.
  • $2$ points for Subtask 4.

채점 및 기타 정보

  • 예제는 채점하지 않는다.