Hide

Problem D
Heaps from Trees

You are given a rooted tree with $n$ nodes. The nodes are labeled $1$ to $n$, and node $1$ is the root. Each node has a value $v_ i$.

You would like to turn this tree into a heap. That is, you would like to choose the largest possible subset of nodes that satisfy this Heap Property: For every node pair $i$,$j$ in the subset, if node $i$ is an ancestor of node $j$ in the tree, then $v_ i > v_ j$. Note that equality is not allowed.

Figure out the maximum number of nodes you can choose to form such a subset. The subset does not have to form a subtree.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will contain a single integer $n$ ($1 \le n \le 2 \cdot 10^5$), which is the number of nodes in the tree. The nodes are numbered $1$ to $n$.

Each of the next $n$ lines will describe the nodes, in order from $i=1$ to $n$. They will each contain two integers $v_ i$ and $p_ i$, where $v_ i$ ($0 \le v_ i \le 10^9$) is the value in the node, and $p_ i$ ($0 \le p_ i < i$) is the index of its parent. Every node’s index will be strictly greater than its parent node’s index. Only node 1, the root, will have $p_1=0$, since it has no parent. For all other nodes ($i=2, 3, \ldots , n$), $1 \le p_ i < i$.

Output

Output a single integer representing the number of nodes in the largest subset satisfying the Heap Property.

Sample Input 1 Sample Output 1
5
3 0
3 1
3 2
3 3
3 4
1
Sample Input 2 Sample Output 2
5
4 0
3 1
2 2
1 3
0 4
5
Sample Input 3 Sample Output 3
6
3 0
1 1
2 1
3 1
4 1
5 1
5
Sample Input 4 Sample Output 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

Please log in to submit a solution to this problem

Log in