Promotion Counting#10553
The cows have once again tried to form a startup company, having apparently forgotten from past experience that cows make terrible managers!
The cows, conveniently numbered 1, \ldots, n, organize the company as a tree, with cow as the president (the root of the tree). Each cow except the president has a single manager (its "parent" in the tree). Each cow has a distinct proficiency rating , which describes how good she is at her job. If cow is an ancestor (for example, a manager, a manager's manager, or higher) of cow , then we say that is a subordinate of .
Unfortunately, the cows find that managers often have lower proficiency ratings than some of their subordinates. In such cases, a manager should consider promoting some of her subordinates. Your task is to help the cows identify when this happens. For each cow , count the number of subordinates such that p(j) > p(i).
The first line contains number n~(1 \le n \le 10^5). The next lines contain the proficiency ratings p(1), \ldots, p(n) of the cows. All proficiency ratings are distinct integers in the range 1, \ldots, 10^9.
The next n - 1 lines describe the manager (parent) of each cow 2, \ldots, n. Recall that cow has no manager, since she is the president.
Print lines. The -th line should contain the number of subordinates of cow whose proficiency rating is higher than that of cow .
Example 1