#2521. 「FJOI2018」领导集团问题

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: spj

题目描述

一个公司的组织领导架构可以用一棵领导树来表示。公司的每个成员对应于树中一个结点 v_i ,且每个成员都有响应的级别 w_i 。越高层的领导,其级别值 w_i 越小。树中任何两个结点之间有边相连,则表示与结点相应的两个成员属于同一部门。领导集团问题就是根据公司的领导树确定公司的最大部门。换句话说,也就是在领导树中寻找最大的部门结点子集,使得的结点 v_i v_j ,如果 v_i v_j 的子孙结点,则 w_i \ge w_j

编程任务:对于任意对于给定的领导树,计算出领导树中最大的部门结点子集。

输入格式

第一行有一个正整数 n ,表示领导树的结点数。接下来的一行中有 n 个整数。第 i 个数表示 w_i 。再接下来的 n - 1 行中,第 i 行有一个整数 v_i 表示 v_i i + 1 的双亲结点。

n 为正整数, n \le 200000 0 < w_i \le 10^9

输出格式

输出找到的最大的部门的成员数。

样例

样例输入

6
2 5 1 3 5 4
1
1
2
2
4

样例输出

4

数据范围与提示

对于 10\% 的数据, n\le 20

对于 40\% 的数据, n\le 2000

对于 100\% 的数据, n\le 200000

测试数据为民间数据,非原题数据。