E. Move and Swap
dfs and similar; dp; greedy; trees
You are given \(n - 1\) integers \(a_2, \dots, a_n\) and a tree with \(n\) vertices rooted at vertex \(1\). The leaves are all at the same distance \(d\) from the root. Recall that a tree is a connected undirected graph without cycles. The distance between two vertices is the number of edges on the simple path between them. All non-root vertices with degree \(1\) are leaves. If vertices \(s\) and \(f\) are connected by an edge and the distance of \(f\) from the root is greater than the distance of \(s\) from the root, then \(f\) is called a child of \(s\).Initially, there are a red coin and a blue coin on the vertex \(1\). Let \(r\) be the vertex where the red coin is and let \(b\) be the vertex where the blue coin is. You should make \(d\) moves. A move consists of three steps: Move the red coin to any child of \(r\). Move the blue coin to any vertex \(b'\) such that \(dist(1, b') = dist(1, b) + 1\). Here \(dist(x, y)\) indicates the length of the simple path between \(x\) and \(y\). Note that \(b\) and \(b'\) are not necessarily connected by an edge. You can optionally swap the two coins (or skip this step). Note that \(r\) and \(b\) can be equal at any time, and there is no number written on the root.After each move, you gain \(|a_r - a_b|\) points. What's the maximum number of points you can gain after \(d\) moves?
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 \leq n \leq 2 \cdot 10^5\)) — the number of vertices in the tree.The second line of each test case contains \(n-1\) integers \(v_2, v_3, \dots, v_n\) (\(1 \leq v_i \leq n\), \(v_i \neq i\)) — the \(i\)-th of them indicates that there is an edge between vertices \(i\) and \(v_i\). It is guaranteed, that these edges form a tree.The third line of each test case contains \(n-1\) integers \(a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^9\)) — the numbers written on the vertices.It is guaranteed that the sum of \(n\) for all test cases does not exceed \(2 \cdot 10^5\).
For each test case, print a single integer: the maximum number of points you can gain after \(d\) moves.
In the first test case, an optimal solution is to: move \(1\): \(r = 4\), \(b = 2\); no swap; move \(2\): \(r = 7\), \(b = 6\); swap (after it \(r = 6\), \(b = 7\)); move \(3\): \(r = 11\), \(b = 9\); no swap. The total number of points is \(|7 - 2| + |6 - 9| + |3 - 9| = 14\). In the second test case, an optimal solution is to: move \(1\): \(r = 2\), \(b = 2\); no swap; move \(2\): \(r = 3\), \(b = 4\); no swap; move \(3\): \(r = 5\), \(b = 6\); no swap. The total number of points is \(|32 - 32| + |78 - 69| + |5 - 41| = 45\).