Maximize the Root
Description
You are given a rooted tree, consisting of $n$ vertices. The vertices in the tree are numbered from $1$ to $n$, and the root is the vertex $1$. The value $a_i$ is written at the $i$-th vertex.
You can perform the following operation any number of times (possibly zero): choose a vertex $v$ which has at least one child; increase $a_v$ by $1$; and decrease $a_u$ by $1$ for all vertices $u$ that are in the subtree of $v$ (except $v$ itself). However, after each operation, the values on all vertices should be non-negative.
Your task is to calculate the maximum possible value written at the root using the aforementioned operation.
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — the initial values written at vertices.
The third line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i \le n$), where $p_i$ is the parent of the $i$-th vertex in the tree. Vertex $1$ is the root.
Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
For each test case, print a single integer — the maximum possible value written at the root using the aforementioned operation.
Input
The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — the initial values written at vertices.
The third line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i \le n$), where $p_i$ is the parent of the $i$-th vertex in the tree. Vertex $1$ is the root.
Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
Output
For each test case, print a single integer — the maximum possible value written at the root using the aforementioned operation.
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
Note
In the first test case, the following sequence of operations is possible:
- perform the operation on $v=3$, then the values on the vertices will be $[0, 1, 1, 1]$;
- perform the operation on $v=1$, then the values on the vertices will be $[1, 0, 0, 0]$.