시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 269 | 92 | 68 | 40.964% |
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을 넘지 않는다.
첫째 줄에 최소 비용을 출력한다.
5 1 0 0 1 1 2 1 2 1 1 2
2