#PU696. USACO 2017 January Contest, Platinum — Problem 1. Promotion Counting
USACO 2017 January Contest, Platinum — Problem 1. Promotion Counting
USACO 2017 January Contest, Platinum — Problem 1. Promotion Counting
题目描述
The cows have once again tried to form a startup company, failing to remember from past experience that cows make terrible managers! The cows, conveniently numbered (), organize the company as a tree, with cow 1 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 (e.g., a manager of a manager of a manager) of cow , then we say is a subordinate of . Unfortunately, the cows find that it is often the case that a manager has less proficiency than several of her subordinates, in which case the manager should consider promoting some of her subordinates. Your task is to help the cows figure out when this is happening. For each cow in the company, please count the number of subordinates where .
输入格式
The first line of input contains . The next lines of input contain the proficiency ratings for the cows. Each is a distinct integer in the range . The next lines describe the manager (parent) for cows . Recall that cow 1 has no manager, being the president.
输出格式
Please print lines of output. The th line of output should tell the number of subordinates of cow with higher proficiency than cow .
数据范围
(见题面原文)
样例
样例 1
5
804289384
846930887
681692778
714636916
957747794
1
1
2
3
2
0
1
0
0
Problem credits: Karthik Nair