P16145 [ICPC 2017 NAIPC] Heaps from Trees

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.