14509번 - 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 ≤ n ≤ 2 · 10⁵), 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 ≤ v_i ≤ 10⁹) is the value in the node, and p_i (0 ≤ 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₁ = 0, since it has no parent. For all other nodes (i = 2..n), 1 ≤ p_i < i.

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