Maximize the Root
Contest: Educational Codeforces Round 168 (Rated for Div. 2)
Difficulty rating: 1500
Tags: binary search, dfs and similar, dp, greedy, trees

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.

Input format:
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 format:
For each test case, print a single integer — the maximum possible value written at the root using the aforementioned operation.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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]$$$.

Example input:
3
4
0 1 0 2
1 1 3
2
3 0
1
5
2 5 3 9 6
3 1 5 2

Example output:
1
3
6

Editorial:
We can clearly say that if some value $$$k$$$ can be obtained at the root, then any value from $$$a_1$$$ to $$$k$$$ can also be obtained. Using that fact, we can use binary search to solve the problem.
Let's fix some value $$$\mathit{mid}$$$ in binary search and check if it is possible to apply an operation from the statement $$$\mathit{mid}$$$ times to the root. Let's write the following recursive function: $$$\mathit{check}(v, x)$$$ — the function that checks whether it is possible to obtain at least $$$x$$$ at all vertices from the subtree of $$$v$$$ (including $$$v$$$ itself) simultaneously (i. e. we had to make $$$x$$$ operations above the current vertex, can the subtree of $$$v$$$ "support" them?).
Let the current state be $$$(v, x)$$$, then there are three cases of transitions:
• $$$v$$$ is a leaf, then $$$x \le a_v$$$ should hold;
• $$$v$$$ is not a leaf and $$$x \le a_v$$$, then the vertex $$$v$$$ is ok, and we have to check its subtree (i. e. $$$\mathit{check}(u, x)$$$ should be true for all $$$u$$$ that are children of $$$v$$$).
• $$$v$$$ is not a leaf and $$$x > a_v$$$, then we have to apply the operation $$$(x - a_v)$$$ times to the vertex $$$v$$$, and that adds an additional constraint on the subtree of $$$v$$$; specifically, $$$\mathit{check}(u, x + (x - a_v))$$$ should be true for all $$$u$$$ that are children of $$$v$$$.
Be careful with overflows: $$$x$$$ might grow exponentially, so you should, for example, return from the function when $$$x$$$ becomes very large.
When we check a single value of $$$mid$$$, this recursive function is called once for each vertex in the tree, so the total time complexity of this solution is $$$O(n\log{A})$$$, where $$$A$$$ is an upper bound of the values of the array $$$a$$$.