[USACO17JAN] Promotion Counting P

题目描述

奶牛们又一次试图创建一家创业公司,还是没有从过去的经验中吸取教训——牛是可怕的管理者! 为了方便,把奶牛从 $1\sim n$ 编号,把公司组织成一棵树,1 号奶牛作为总裁(这棵树的根节点)。除了总裁以外的每头奶牛都有一个单独的上司(它在树上的 “双亲结点”)。 所有的第 $i$ 头牛都有一个不同的能力指数 $p_i$,描述了她对其工作的擅长程度。如果奶牛 $i$ 是奶牛 $j$ 的祖先节点,那么我们我们把奶牛 $j$ 叫做 $i$ 的下属。 不幸地是,奶牛们发现经常发生一个上司比她的一些下属能力低的情况,在这种情况下,上司应当考虑晋升她的一些下属。你的任务是帮助奶牛弄清楚这是什么时候发生的。简而言之,对于公司的中的每一头奶牛 $i$,请计算其下属 $j$ 的数量满足 $p_j > p_i$。

输入输出格式

输入格式


输入的第一行包括一个整数 $n$。 接下来的 $n$ 行包括奶牛们的能力指数 $p_1,p_2 \dots p_n$。保证所有数互不相同。 接下来的 $n-1$ 行描述了奶牛 $2 \sim n$ 的上司的编号。再次提醒,1 号奶牛作为总裁,没有上司。

输出格式


输出包括 $n$ 行。输出的第 $i$ 行应当给出有多少奶牛 $i$ 的下属比奶牛 $i$ 能力高。

输入输出样例

输入样例 #1

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3

输出样例 #1

2
0
1
0
0

说明

对于 $100\%$ 的数据,$1\le n \le 10^5$,$1 \le p_i \le 10^9$。