주차장 안내 데스크 배치

문제

한 대형 주차장에는 구역이 N개 있고, 구역 사이를 잇는 도로가 N-1개 있어서 어느 두 구역도 도로를 따라 서로 오갈 수 있다. 즉 주차장의 구조는 트리이다. 구역에는 1번부터 N번까지 번호가 붙어 있고, i번째 도로는 구역 u_i와 v_i를 양방향으로 연결하며 걸어서 w_i분이 걸린다. 운영팀은 서로 다른 K개의 구역을 골라 안내 데스크를 설치하려 한다. 각 구역에서 가장 가까운 안내 데스크가 있는 구역까지 도로를 따라 걷는 최소 시간을 그 구역의 대기 거리라고 하며, 데스크가 설치된 구역의 대기 거리는 0이다. 데스크를 어디에 설치할지 잘 골라 모든 구역의 대기 거리 중 최댓값이 가능한 한 작아지게 할 때, 그 최솟값을 구하는 프로그램을 작성한다. 답은 항상 정수이다. 데스크는 구역에만 설치할 수 있고 도로 중간에는 설치할 수 없다. K가 N과 같으면 모든 구역에 설치하므로 답은 0이다.

입력

첫 줄에 구역 수 N과 데스크 수 K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ K ≤ N) 다음 N-1개의 줄에 각각 정수 u_i, v_i, w_i가 공백으로 구분되어 주어진다. (1 ≤ u_i, v_i ≤ N, 1 ≤ w_i ≤ 1,000)

출력

모든 구역의 대기 거리 중 최댓값의 최솟값을 한 줄에 출력한다.

5 2
1 2 1
2 3 1
3 4 1
4 5 1

1

5 1
1 2 3
1 3 4
1 4 2
4 5 6

6

1 1

0

출처: Devin.KR 자체 제작