题目描述

You are given a rooted tree with $n$ nodes. The nodes are labeled $1..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.

输入格式

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 \leq n \leq 2 \cdot 10^5$), which is the number of nodes in the tree. The nodes are numbered $1..n$.

Each of the next $n$ lines will describe the nodes, in order. They will each contain two integers $v_i$ and $p_i$, where $v_i$ ($0 \leq v_i \leq 10^9$) is the value in the node, and $p_i$ ($0 \leq 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..n$), $1 \leq p_i < i$.

输出格式

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

5
3 0
3 1
3 2
3 3
3 4

1

5
4 0
3 1
2 2
1 3
0 4

5

6
3 0
1 1
2 1
3 1
4 1
5 1

5

11
7 0
8 1
5 1
5 2
4 2
3 2
6 3
6 3
10 4
9 4
11 4

7