给你一棵有根的树，由 n个顶点组成。树中的顶点编号为 1 至 n ，根顶点为 1 。值 ai 写在第 i个顶点上。
您可以执行以下任意次数(可能为零)的操作：选择一个顶点 v，该顶点至少有一个子顶点；之后将 av 增加 1 ；并将 au 减少 1 ，（顶点u是v 的子树中所有顶点( v 本身除外)）。不过，每次操作后，所有顶点上的值都应为非负（即不可通过操作使得某个顶点变成负数）。
换句话说，每次操作选择一个顶点，将该顶点的值+1，其子树上的所有节点都-1，同时操作不可使得有顶点的值变为负数。
您的任务是通过上述操作计算出写入根的最大可能值。
第一行包含一个整数 t ( 1≤t≤104) - 测试用例数。
每个测试用例的第一行包含一个整数 n ( 2≤n≤2⋅105) - 树中的顶点数。
第二行包含 n 个整数 a1,a2,…,an ( 0≤ai≤109)。( 0≤ai≤109) - 写入顶点的初始值。
第三行包含 n−1个整数 p2,p3,…,pn ( 1≤pi≤n)，其中 pi是树中第 i个顶点的父节点。顶点 1是树根。
输入的附加限制：所有测试用例的 n之和不超过 2⋅105 。
3
4
0 1 0 2
1 1 3
2
3 0
1
5
2 5 3 9 6
3 1 5 2
1
3
6
在第一个测试案例中，可以进行以下一系列操作：
- 对 v=3 执行操作，则顶点上的值为 [0, 1, 1, 1] ；
- 对 v=1 执行操作，则顶点上的值为 [1, 0, 0, 0] 。
Anything about this OnlineJudge, Please Contact Administrator.
Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部