시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB234836041.958%

문제

N(1 ≤ N ≤ 10,000)개의 정점을 갖는 루트 있는 트리(Rooted Tree)를 생각해 보자. 각각의 간선에는 음 아닌 정수로 가중치가 있다. 이 트리의 높이는 루트에서 가장 멀리 떨어져 있는 정점까지의 거리를 의미한다.

이 트리의 간선의 가중치를 1씩 줄일 때마다 1만큼의 비용이 든다. 쉽게 생각하면, 가중치가 x인 간선의 가중치를 y(x ≥ y ≥ 0)로 줄일 때, x - y만큼의 비용이 든다는 의미이다. 문제를 쉽게 하기 위해서 음 아닌 정수에서 음 아닌 정수로 줄이는 경우만 생각하기로 하자.

우리는 몇 개의 간선의 가중치를 적절히 줄여서, 이 트리의 높이를 H(0 ≤ H ≤ 150,000, H는 정수)로 만들려고 한다. 이때, 최소의 비용을 들여서 높이를 H로 만드는 것이 목적이다.

입력

첫째 줄에 정점의 개수 N과 H가 주어진다. 다음 N개의 줄에는 1번 정점부터 N번 정점까지 차례로, 각 정점의 부모 정점과, 그 정점에서 부모 정점까지의 거리(간선의 가중치)가 주어진다. 루트의 경우에는 부모 정점과 비용 대신에 0 두 개가 주어진다. 가중치는 음이 아닌 정수이고, 각 간선의 가중치의 총 합은 1,000,000,000을 넘지 않는다.

출력

첫째 줄에 최소 비용을 출력한다.

예제 입력 1

5 1
0 0
1 1
2 1
2 1
1 2

예제 출력 1

2

출처

  • 문제의 오타를 찾은 사람: jason9319