P4577 [FJOI2018] Leadership Group Problem

A company’s leadership structure can be represented by a leadership tree. Each company member corresponds to a node $v_i$ in the tree, and each member has a corresponding level $w_i$. The higher the leader is in the hierarchy, the smaller their level value $w_i$ is. If there is an edge between any two nodes in the tree, it means the two corresponding members belong to the same department. The leadership group problem is to determine the company’s largest department based on the leadership tree. In other words, we need to find the largest subset of nodes in the leadership tree such that for any nodes $v_i$ and $v_j$, if $v_i$ is a descendant of $v_j$, then $w_i \ge w_j$. Programming task: For any given leadership tree, compute the size of the largest valid department node subset in the leadership tree.

The first line contains a positive integer $n$, denoting the number of nodes in the leadership tree. The next line contains $n$ integers. The $i$-th number denotes $w_i$. In the following $n - 1$ lines, the $i$-th line contains an integer $v_i$, meaning that $v_i$ is the parent of node $i + 1$.

Output the number of members in the largest department found.

For $10\%$ of the testdata, $n \le 20$. For $40\%$ of the testdata, $n \le 2000$. For $100\%$ of the testdata, $1 \le n \le 2 \times 10 ^ 5$, $0 < w_i \le 10 ^ 9$. Translated by ChatGPT 5