A90389.「FJOI2018」领导集团问题
省选/NOI-
通过率:0%
时间限制:1.00s
内存限制:256MB
题目描述
一个公司的组织领导架构可以用一棵领导树来表示。公司的每个成员对应于树中一个结点 vi,且每个成员都有响应的级别 wi。越高层的领导,其级别值 wi 越小。树中任何两个结点之间有边相连,则表示与结点相应的两个成员属于同一部门。领导集团问题就是根据公司的领导树确定公司的最大部门。换句话说,也就是在领导树中寻找最大的部门结点子集,使得的结点 vi 和 vj,如果 vi 是 vj 的子孙结点,则 wi≥wj。
编程任务:对于任意对于给定的领导树,计算出领导树中最大的部门结点子集。
输入格式
第一行有一个正整数 n,表示领导树的结点数。接下来的一行中有 n 个整数。第 i 个数表示 wi。再接下来的 n−1 行中,第 i 行有一个整数 vi 表示 vi 是 i+1 的双亲结点。
n 为正整数,n≤200000,0<wi≤109。
输出格式
输出找到的最大的部门的成员数。
输入输出样例
输入#1
6 2 5 1 3 5 4 1 1 2 2 4
输出#1
4
说明/提示
对于 10% 的数据,n≤20;
对于 40% 的数据,n≤2000;
对于 100% 的数据,n≤200000。
测试数据为民间数据,非原题数据。