Tree Maximum Pruning Sum

In this problem, you are given a rooted tree with (n) nodes numbered from (1) to (n). Node (1) is the root of the tree. Each node (i) has an associated integer value (v_i). For nodes (2 \le i \le n), you are also given its parent node (p_i). You can prune (i.e., remove) any subtree (which means deleting a node and all of its descendants). The goal is to prune the tree optimally so that the sum of the values of the remaining nodes is maximized. Note that it might be optimal to remove an entire subtree if its total sum is negative.

The problem can be formulated recursively as follows. Let (f(u)) denote the maximum sum achievable for the subtree rooted at node (u). Then,

[ f(u) = v_u + \sum_{v \in \text{children}(u)} \max(0, f(v)) ]

Your task is to compute (\max(0, f(1))), the maximum achievable sum for the entire tree after pruning optimally.

Example: For example, consider a tree with 6 nodes where the values are [2, -3, 4, -2, 6, 1] and the parent relationships are given by [1, 1, 3, 3, 5] (which means node 2 and node 3 have parent 1, node 4 and node 5 have parent 3, and node 6 has parent 5). The maximum sum obtainable after optimal pruning is 13.

inputFormat

The input is read from standard input (stdin) and consists of multiple test cases. The first line contains a single integer (T) (at least 3 test cases).

For each test case:

• The first line contains an integer (n), the number of nodes in the tree.
• The second line contains (n) integers representing the values of the nodes (v_1, v_2, \dots, v_n).
• If (n > 1), the third line contains (n-1) integers representing the parent of nodes (2 \dots n) (i.e. (p_2, p_3, \dots, p_n)). For (n = 1), the third line is omitted.

outputFormat

For each test case, output a single integer on a separate line which represents the maximum sum of the remaining nodes' values after the optimal pruning, printed to standard output (stdout).## sample

6
6
2 -3 4 -2 6 1
1 1 3 3 5
4
5 3 4 2
1 1 2
3
-1 -2 -3
1 1
5
1 -2 3 -4 5
1 1 3 3
1
10
7
-10 10 10 -5 5 5 -10
1 2 2 3 3 4

13
14
0
9
10
20