Promotion Counting

题目描述

奶牛们又一次试图创办一家创业公司，但她们忘了过去的经验：奶牛当经理实在太糟糕了！ 奶牛们方便地编号为 $1 \ldots N$（$1 \leq N \leq 100,000$），并将公司组织成一棵树，其中 1 号奶牛是总裁（树的根）。除总裁外，每头奶牛都有且仅有一个经理（即树中的“父节点”）。每头奶牛 $i$ 都有一个互不相同的熟练度评分 $p(i)$，表示她的工作能力。如果奶牛 $i$ 是奶牛 $j$ 的祖先（例如：经理的经理的经理），那么我们称 $j$ 是 $i$ 的下属。 不幸的是，奶牛们发现经常会出现经理的熟练度低于她的若干下属的情况，这时经理就应该考虑提拔一些下属。你的任务是帮助奶牛们判断这种情况何时发生。对于公司中的每头奶牛 $i$，请统计满足 $p(j) > p(i)$ 的下属 $j$ 的数量。

输入格式

第一行输入 $N$。 接下来 $N$ 行输入给出奶牛的熟练度评分 $p(1) \ldots p(N)$。每个评分都是互不相同的整数，范围为 $1 \ldots 1,000,000,000$。 接下来 $N-1$ 行描述奶牛 $2 \ldots N$ 的经理（父节点）。注意 1 号奶牛是总裁，没有经理。

输出格式

请输出 $N$ 行。 第 $i$ 行应输出奶牛 $i$ 的下属中，熟练度高于奶牛 $i$ 的数量。

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3

2
0
1
0
0

提示

题目来源：Karthik Nair

标签: USACO|2017|Platinum

来源

USACO|2017|Platinum