bzoj#P4756. [USACO2017 Jan] Promotion Counting

[USACO2017 Jan] Promotion Counting

题目描述

nn 只奶牛构成了一个树形的公司,每个奶牛有一个能力值 pip_i11 号奶牛为树根。

问对于每个奶牛来说,它的子树中有几个能力值比它大的。

输入格式

第一行一个正整数 nn,表示有几只奶牛。

接下来 nn 行为 1n1\cdots n 号奶牛的能力值 pip_i

接下来 n1n-1 行为 2n2\cdots n 号奶牛的经理(树中的父亲)。

输出格式

nn 行,每行输出奶牛 ii 的下属中有几个能力值比 ii 的大。

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3
2
0
1
0
0

数据规模与约定

对于 100%100\% 的数据,1n1051\le n\le 10^5

题目来源

Platinum 鸣谢 Acty 提供译文。