문제
1번 노드가 루트이고 가중치가 부여된 노드가 N개 있다.
i번째 노드에 부여된 가중치는 vi이다.
상수는 이 트리에서 정점을 적당히 선택해서 힙으로 만들고 싶다.
그래서 상수는 다음 조건을 만족하는 정점 집합을 선택하기로 했다.
선택된 노드들이 부분트리를 이룰 필요는 없다. 단지 아래 조건을 만족하면 된다.
"집합에 포함된 모든 정점쌍 i, j에 대해서, 정점 i가 정점 j의 조상이라면, vi > vj이다." (부등호에 등호가 없음에 유의하자)
가능한 정점 집합들 중 정점 갯수의 최댓값을 구해 상수에게 알려주자.
입력
첫 번째 줄에는 노드의 수 N (2 ≤ N ≤ 300,000)이 주어진다.
두 번째 줄부터 N개의 줄에 가중치를 의미하는 정수 vi와 부모 정점 pi가 주어진다. (0≤vi≤109)
부모 정점은 자신보다 번호가 항상 작음이 보장된다.
1번 정점만은 루트이므로 p1=0이며, 다른 노드에 한해서 1 ≤ pi < i를 만족한다.
출력
첫 번째 줄에 조건을 만족하는 정점 집합들 중 정점 개수의 최댓값을 출력한다.
예제 #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
11
7 0
8 1
5 1
5 2
4 2
3 2
6 3
6 3
10 4
9 4
11 4
7
출처
20201031 집중강화학습4차5번, songc,North American Invitational Programming Contest 2017
로그인해야 코드를 작성할 수 있어요.