Wonderful Tree!
Contest: EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2)
Difficulty rating: 2000
Tags: brute force, data structures, dfs and similar, dsu, greedy, trees

You are given a tree with $$$n$$$ vertices, rooted at vertex $$$1$$$. The $$$i$$$-th vertex has an integer $$$a_i$$$ written on it.

Let $$$L$$$ be the set of all direct children$$$^{\text{∗}}$$$ of $$$v$$$. A tree is called wonderful, if for all vertices $$$v$$$ where $$$L$$$ is not empty, $$$$$$a_v \le \sum_{u \in L}{a_u}.$$$$$$ In one operation, you choose any vertex $$$v$$$ and increase $$$a_v$$$ by $$$1$$$.

Find the minimum number of operations needed to make the given tree wonderful!

Input format:
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5000$$$) — the number of vertices in the tree.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the values initially written on the vertices.

The third line of each test case contains $$$n - 1$$$ integers $$$p_2, p_3 , \ldots, p_n$$$ ($$$1 \le p_i < i$$$), indicating that there is an edge from vertex $$$p_i$$$ to vertex $$$i$$$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output format:
For each test case, output a single integer — the minimum number of operations needed to make the tree wonderful.

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

Note:
The tree in the first test case:

You can apply the operation once on vertex $$$5$$$ and twice on vertex $$$2$$$ to get a wonderful tree.

In the second test case, you can apply the operation twice on vertex $$$2$$$ to get a wonderful tree.

In the third and fourth test cases, the tree is already wonderful, so you don't need to apply any operations.

Example input:
4
5
9 3 4 1 2
1 1 3 3
2
5 3
1
2
36 54
1
3
0 0 0
1 2

Example output:
3
2
0
0

Editorial:
Let $$$b_v := \sum_{u \in L}{a_u} - a_v$$$ if $$$L$$$ is not empty and $$$b_v := +\infty$$$ otherwise. Then, in one operation we decrease $$$b_v$$$ by $$$1$$$ and increase $$$b_{p_v}$$$ by $$$1$$$ ($$$p_v$$$ is the parent of $$$v$$$), and our objective is to make $$$b_v \ge 0$$$ for all vertices $$$v$$$ in as few operations as possible.
We can actually chain our operations to form a more powerful one. In particular, the new operation becomes:
• Select two vertices $$$v$$$ and $$$w$$$ such that $$$d_v \le d_w$$$ and $$$v$$$ is an ancestor of $$$w$$$ by paying $$$d_w - d_v$$$ coins, where $$$d_v$$$ is the depth of vertex $$$v$$$.
• Decrease $$$b_w$$$ by $$$1$$$ and increase $$$b_v$$$ by $$$1$$$.
Suppose one optimal sequence of operations applies the operations on the pairs of vertices $$$(v_1, w_1)$$$ and $$$(v_2, w_2)$$$ and the paths $$$v_1 \rightarrow w_1$$$ and $$$v_2 \rightarrow w_2$$$ intersect. Then, applying the operations on the pairs of vertices $$$(v_1, w_2)$$$ and $$$(v_2, w_1)$$$, is not less optimal since $$$(d_{w_1} - d_{v_1}) + (d_{w_2} - d_{v_2}) = (d_{w_2} - d_{v_1}) + (d_{w_1} - d_{v_2})$$$. This means that we can choose which operations to apply on lower $$$v$$$ without caring about its ancestors.
Suppose that after some sequence of operations, which includes the operation $$$(v, w)$$$, there is a vertex $$$u$$$ in the subtree of $$$v$$$ with $$$d_u < d_w$$$ and $$$b_u > 0$$$. Then, it is optimal to apply the operation on $$$(v, u)$$$ instead of $$$(v, w)$$$. This means that we want to apply the operation on the closest vertices in the subtree of $$$v$$$.
The two observations above lead to a greedy. We will iterate over all $$$v$$$ from $$$n$$$ to $$$1$$$, and while $$$b_v$$$ is less than zero, keep applying the operation on $$$(v, u)$$$, where $$$u$$$ is the closest vertex in the subtree of $$$v$$$ with $$$b_u > 0$$$. This is possible to implement in a number of ways, one of them includes running a bfs from each vertex $$$v$$$.
Complexity: $$$\mathcal{O}(n^2)$$$
Note: it is possible to solve this problem faster, up to only $$$\mathcal{O}(n)$$$ time.