CF1997D Maximize the Root

题目描述

给你一棵有根的树，由 $n$ 个顶点组成。树上的顶点从 $1$到 $n$ 编号，根是顶点 $1$ 。第 $i$ 个顶点上的值为 $a_i$。

你可以执行以下操作任意次(可以为零次):选择一个至少有一个子顶点的顶点 $v$; 将 $a_v$ 增加 $1$ 并且对于 $v$ 的子树中的所有顶点 $u$ 将 $a_u$ 减少 $1$ (除了 $v$ 本身)。但是，在每次操作之后，所有顶点上的值都应该是非负的。

你的任务是使用前面提到的运算来计算写在根上的最大可能值。

输入格式

第一行包含一个整数 $t(1 \le t \le 10^4)$ 表示测试用例的数量。

每个测试用例的第一行为一个整数 $n (2 \le n \le 2 \times 10^5)$ 表示树中顶点的数量。

第二行包含 $n$ 整数 $a_1, a_2, \dots, a_n$ ( $0 \le a_i \le 10^9$ ) 表示每个点的初始值。

第三行包含 $n - 1$ 整数 $p_2，p_3，\dots，p_n (1 \le p_i \le n)$，其中 $p_i$ 是树中第 $i$ 个顶点的父顶点。顶点 $1$ 是根。

对输入的附加约束:所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数——使用前面提到的操作在根上写出的最大可能值。

输入输出样例 #1

输入 #1

3
4
0 1 0 2
1 1 3
2
3 0
1
5
2 5 3 9 6
3 1 5 2

输出 #1

1
3
6