3208 - 权值统计
题目描述
一棵树包含了 N 个点（编号 1 \sim N）和 N-1 条边，编号为 1 的点为树的根。树上编号为 i 的点权值为 V_i。
对于每个结点，如果该结点编号为 i，请编程计算出，该结点的所有子孙结点中，共有多少个结点的权值大于结点 i 的权值。
输入
第 1 行输入一个整数 N。
接下来 N 行，共有 N 个互不相等的整数 V_1 \sim V_n，分别代表编号为 1 的点到编号为 N 的点的权值。
接下来 N - 1 行，共有 N-1 个整数 F_2 \sim F_n，分别代表编号为 2 的点到编号为 N 的点的父结点编号，请特别注意，编号为 1 的结点为树根，因此不需要读入该结点的父结点。
输出
输出 N 行，每行一个整数，第 i 行请输出对于编号为 i 的点，其所有子孙结点中权值大于 V_i 的结点总数。
样例
输入
5 6 2 9 14 7 1 1 3 4
输出
3 0 1 0 0
输入
10 12 3 20 10 16 7 17 19 5 11 1 2 1 4 4 5 1 8 6
输出
4 1 0 3 1 1 0 0 0 0
输入
20 2 18 29 21 5 17 26 16 20 15 28 7 27 1 9 3 22 19 4 24 1 2 1 1 5 6 7 7 5 5 4 6 1 5 6 15 15 4 18
输出
18 1 0 0 11 3 0 0 0 0 0 0 0 0 3 0 0 1 0 0
说明
样例 1 解释
样例 1 如上图所示。
1 号的结点的子孙中，3、4、5 结点的权值比点 1 的权值大。
2 号没有子孙结点。
3 号的结点的子孙中，4 结点的权值比点 3 的权值大。
4 号没有比自己权值大的子孙结点。
5 号没有子孙结点。
数据范围
对于 30\% 的数据，满足 1 \le N \le 200。
对于 60\% 的数据，满足 1 \le N \le 10^4。
对于 100\% 的数据，满足 1 \le N \le 10^5，1 \le V_i \le 10^9，1 \le F_i \le N。
标签