초원에서 질주하기

시간 제한3초메모리 제한1024 MB

요약

가중치가 있는 트리 형태의 마을 n개에 소방서 f개를 세워, 어느 마을에서든 가장 가까운 소방서까지 가는 거리의 최댓값을 최소로 만드는 문제입니다.

난이도: 보통10점 중 6점
유형: 트리, 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

바닥까지 밟힌 가스 페달. 끼익거리는 타이어. 울부짖는 사이렌. 긴급 차량은 목적지에 최대한 빨리 도착하려고 필요한 모든 일을 한다. 생명이 걸린 경우가 많으므로 시간은 매우 중요하다.

긴급 서비스를 제공하는 일은 언제나 어렵다. 특히 카자흐 스텝처럼 인구가 드문 지역은 더 그렇다. 인구에 비해 인프라를 짓는 비용이 높다. 따라서 도로 수와 차량 수를 모두 줄이는 것이 중요하다. 반면 긴급 서비스의 응답 시간도 최소화해야 한다.

이 문제의 도로망은 이미 도로 수가 최소인 상태이다. 즉 임의의 두 마을은 정확히 하나의 경로로 연결된다. 카자흐 스텝 소방국은 정부 보조금으로 새 소방차를 몇 대 확보했다. 소방국은 일부 마을에 소방서를 세우고 소방차를 배정하여, 보장되는 응답 시간이 최적이 되도록 하려고 한다.

목표는 소방차가 어떤 마을이든 도달하는 데 걸리는 시간을 최소화하는 소방차 배치를 찾는 것이다. 소방대 편성과 엔진 시동에 걸리는 시간, 마을을 지나는 시간은 무시한다. 응답 시간은 오직 도로를 따라 이동하는 시간으로만 정해진다.

입력

첫 줄에는 두 정수 마을 수 $n$ 과 소방차 수 $f$ 가 주어진다. $1 ≤ n ≤ 100000$ , $1 ≤ f ≤ n$ 이다.

이어서 $n-1$ 개의 줄이 주어진다. $i$ 번째 줄(2 ≤ i ≤ n)에는 두 정수 $v_i$ 와 $t_i$ 가 주어진다. 이는 마을 $i$ 와 마을 $v_i$ 를 잇는 양방향 도로가 있고, 이동 시간이 $t_i$ 임을 뜻한다. $1 ≤ v_i < i$ , $1 ≤ t_i ≤ 10000$ 이다.

출력

$f$ 개의 마을에 소방차를 배치했을 때 보장할 수 있는 최소 응답 시간을 출력한다.

예제2

예제 1
입력
```
6 2
1 8
2 7
2 7
3 6
3 5
```
예상 출력
```
8
```
예제 2
입력
```
3 3
1 1000
2 1000
```
예상 출력
```
0
```