오름차순 트리

시간 제한1초메모리 제한256 MB

요약

루트가 있는 트리에서 각 부모의 라벨이 모든 자식보다 크도록 라벨을 1씩 바꿀 때 드는 최소 비용을 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 트리, 힙
정답자: 아직 제출이 없습니다

문제

루트가 있는 트리가 주어집니다. 트리의 각 정점에는 정수 레이블이 붙어 있습니다. 1달러를 내면 정점 하나의 레이블을 1만큼 증가시키거나 감소시킬 수 있습니다.

각 정점의 레이블이 그 정점의 자식들에 붙은 어떤 레이블보다도 엄격하게 커야 합니다. 이 조건을 만족하는 데 필요한 최소 비용을 구하세요.

입력

첫 번째 줄에는 두 정수가 주어집니다. 트리의 정점 개수 $N$ 과 루트에 붙은 레이블 $C\_1$ 입니다. 정점은 1부터 $N$ 까지 번호가 매겨져 있고, 루트는 정점 1입니다 ( $1 \le N \le 10^5$ ).

이어지는 $N - 1$ 개의 줄은 루트가 아닌 정점을 설명합니다. $i$ 번째 줄에는 정점 $i$ 의 부모 번호 $P\_i$ 와 정점 $i$ 에 붙은 레이블 $C\_i$ 가 주어집니다 ( $1 \le P\_i < i$ , $-10^9 \le c\_i \le 10^9$ ).

출력

최소 비용을 한 줄에 출력합니다.

힌트

왼쪽 그림은 첫 번째 샘플의 입력 상태입니다. 오른쪽 그림은 가능한 최종 상태로, 각 부모의 레이블이 자식의 레이블보다 큽니다.

예제2

예제 1
입력
```
8 6
1 1
2 1
2 3
1 9
5 6
6 6
6 2
```
예상 출력
```
8
```
예제 2
입력
```
4 5
1 5
2 5
3 5
```
예상 출력
```
4
```