ZOJ Problem Set - 2866
Incredible Crazily Progressing Company (ICPC) is facing the problem of overstaffing. It contains several departments and each department may also have underlying departments. Each department may have some managers. Today, the leading manager of the company wants to reduce the stafftrimmer. However, he doesn't know which department has most redundant managers. He needs you to find the number of underlying departments that have more managers than that department for each department.
The first line of each test case contains a positive integer n not exceeding 50000, indicating the number of departments that number from 0 to n - 1. The next line contains n - 1 integers, the i-th of which indicates the i-th department's superior department and is less than i. Note that all the departments except the zeroth has a superior department and they are all the zeroth one's underlying departments. The third line contains n integers not exceeding 1000000, indicating the number of managers of each department.
Output n integers in a line indicating the number of underlying departments that have more managers than that department in the order according to the department number.
6 0 0 1 2 2 10 7 4 8 5 12
1 1 2 0 0 0
Hint: Department 5 has more managers than Department 0. Department 3 has more managers than Department 1. Department 4 and 5 have more managers than Department 2.
Author: GUAN, Yao
Source: ZOJ Monthly, June 2007