#P4756. [Usaco2017 Jan]Promotion Counting

    ID: 3876 传统题 1000ms 128MiB 尝试: 662 已通过: 317 难度: 4 上传者: 标签>难度分类普及+/提高-树算法DFS 序子树转区间离线与分治离线查询查询排序数据结构树状数组CF1600

[Usaco2017 Jan]Promotion Counting

题目描述

奶牛们又成立了一家创业公司。公司由 nn 头奶牛组成,编号从 11 到 nn。它们的上下级关系构成一棵树,11 号奶牛是总裁,其余每头奶牛各有一名直接上司。

每头奶牛 ii 有一个能力值 pip_i,所有能力值互不相同。若奶牛 ii 是奶牛 jj 的祖先,则 jj 是 ii 的下属。直接和间接下属都计入。

公司希望了解哪些下属可以晋升。请对每头奶牛 ii,求有多少名下属 jj 的能力值满足 pj>pip_j>p_i。

输入格式

第一行包含一个整数 nn。

接下来 nn 行依次给出 11 号到 nn 号奶牛的能力值,每行一个整数。

再接下来 n−1n-1 行依次给出 22 号到 nn 号奶牛的直接上司的编号,每行一个整数。总裁没有上司。

输出格式

输出 nn 行,第 ii 行为能力值严格高于奶牛 ii 的下属人数。

样例 #1

样例输入 #1

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3

样例输出 #1

2
0
1
0
0

数据范围

1≤n≤1051\le n\le10^5,1≤pi≤1091\le p_i\le10^9,且各能力值互不相同。