题目描述

给你一棵包含 $n$ 个节点的有根树。树上节点编号从 $1$ 到 $n$，根节点编号为 $1$。初始时节点 $i$ 的权值为 $a_i$。

你可以执行任意次（可以是零次）如下操作：

选择树上的任意一个 非叶子节点 $u$，将 $a_u$ 的数值增加 $1$，同时将以节点 $u$ 为根的子树中的所有其它节点的权值减去 $1$。但是你必须保证操作后树上每个节点的权值均为非负整数。

你希望最终根节点的权值 $a_1$ 最大。求最终能够得到的根节点的最大权值。

输入格式

第一行，一个整数 $n(2 \le n \le 2 \cdot 10^5)$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n(0 \le a_i \le 10^9)$，表示初始时每个节点的权值。

第三行，$n-1$ 个整数 $p_2, p_3, \ldots, p_n(1 \le p_i \le n)$。其中 $p_i$ 表示节点 $i$ 的父节点编号。

输出格式

输出一个整数，表示最终能够得到的根节点的最大权值。

样例

4
0 1 0 2
1 1 3

1

2
3 0
1

3

5
2 5 3 9 6
3 1 5 2

6

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 10, a_i \le 100$
• 对于 $50\%$ 的数据，$n \le 1000, a_i \le 10^5$
• 对于 $100\%$ 的数据，$2 \le n \le 10^5, 0 \le a_i \le 10^9$