트리로 만드는 힙

시간 제한2초메모리 제한512 MB

요약

각 노드에 값이 있는 루트 트리에서, 조상과 자손 관계인 모든 쌍이 조상의 값이 더 크도록 하는 가장 큰 부분집합의 크기를 구한다.

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

문제

노드가 $n$ 개인 루트 있는 트리가 주어진다. 노드에는 $1$ 부터 $n$ 까지 번호가 붙어 있고 $1$ 번 노드가 루트이다. 각 노드 $i$ 에는 값 $v_i$ 가 적혀 있다.

이 트리를 힙으로 만들려고 한다. 즉 다음 힙 성질을 만족하는 노드 부분집합 중 가장 큰 것을 고르려고 한다. 부분집합에 속한 모든 노드 쌍 $i, j$ 에 대해, 트리에서 노드 $i$ 가 노드 $j$ 의 조상이라면 $v_i > v_j$ 이어야 한다.

값이 같은 경우는 허용되지 않는다. 이런 부분집합으로 고를 수 있는 노드 개수의 최댓값을 구하라. 고른 부분집합이 서브트리를 이룰 필요는 없다.

입력

입력은 테스트 케이스 하나로 이루어진다.

첫째 줄에 트리의 노드 개수 $n$ ( $1 \le n \le 2 \times 10^5$ )이 주어진다. 노드 번호는 $1$ 부터 $n$ 까지이다.

다음 $n$ 개의 줄에는 노드 정보가 번호 순서대로 주어진다. $i$ 번째 줄에는 두 정수 $v_i$ 와 $p_i$ 가 주어진다. $v_i$ ( $0 \le v_i \le 10^9$ )는 노드에 적힌 값이고 $p_i$ ( $0 \le p_i < i$ )는 부모 노드의 번호이다. 모든 노드의 번호는 부모 노드의 번호보다 크다. 부모가 없는 루트인 $1$ 번 노드만 $p_1 = 0$ 이고, 나머지 노드 ( $i = 2, \ldots, n$ )는 $1 \le p_i < i$ 이다.

출력

힙 성질을 만족하는 부분집합 중 가장 큰 것의 노드 개수를 정수 하나로 출력한다.

예제4

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

예제 4

입력

예상 출력