Move and Swap
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?
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$$$.
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.
from collections import deque
for _ in range(int(input())):
    N = int(input())
    X = [[] for i in range(N)]
    pp = [int(a) - 1 for a in input().split()]
    for (i, p) in enumerate(pp, 1):
        X[i].append(p)
        X[p].append(i)
    P = [-1] * N
    Q = deque([0])
    R = []
    Y = [[0]]
    D = [0] * N
    while Q:
        i = deque.popleft(Q)
        R.append(i)
        for a in X[i]:
            if a != P[i]:
                P[a] = i
                X[a].remove(i)
                deque.append(Q, a)
    for i in R[1:]:
        D[i] = D[P[i]] + 1
        while len(Y) <= D[i]:
            Y.append([])
        Y[D[i]].append(i)
    A = [0] + [int(a) for a in input().split()]
    d = max(D) + 1
    MI = [10 ** 9] * d
    MA = [0] * d
    S = [0] * N
    for (i, a) in enumerate(A):
        MI[D[i]] = min(MI[D[i]], a)
        MA[D[i]] = max(MA[D[i]], a)
    for i in Y[-1]:
        S[i] = max(abs(A[i] - MA[-1]), abs(A[i] - MI[-1]))
    for de in range(d - 1)[::-1]:
        abc1 = 0
        abc2 = -10 ** 9
        for i in Y[de]:
            ma = 0
            for j in X[i]:
                ma = max(ma, S[j])
            abc1 = max(abc1, ma + A[i])
            abc2 = max(abc2, ma - A[i])
            S[i] = max(abs(A[i] - MI[de]), abs(MA[de] - A[i])) + ma
        for i in Y[de]:
            S[i] = max(S[i], abc1 - A[i], abc2 + A[i])
    print(S[0])
from collections import deque
for _ in range(int(input())):
    N = int(input())
    X = [[] for i in range(N)]
    pp = [int(a) - 1 for a in input().split()]
    for (i, p) in enumerate(pp, 1):
        X[i].append(p)
        X[p].append(i)
    P = [-1] * N
    Q = deque([0])
    R = []
    while Q:
        i = deque.popleft(Q)
        R.append(i)
        for a in X[i]:
            if a != P[i]:
                P[a] = i
                X[a].remove(i)
                deque.append(Q, a)
    Y = [[0]]
    D = [0] * N
    for i in R[1:]:
        D[i] = D[P[i]] + 1
        while len(Y) <= D[i]:
            Y.append([])
        Y[D[i]].append(i)
    A = [0] + [int(a) for a in input().split()]
    d = max(D) + 1
    MI = [10 ** 9] * d
    MA = [0] * d
    for (i, a) in enumerate(A):
        MI[D[i]] = min(MI[D[i]], a)
        MA[D[i]] = max(MA[D[i]], a)
    S = [0] * N
    for i in Y[-1]:
        S[i] = max(abs(A[i] - MA[-1]), abs(A[i] - MI[-1]))
    for de in range(d - 1)[::-1]:
        abc1 = 0
        abc2 = -10 ** 9
        for i in Y[de]:
            ma = 0
            for j in X[i]:
                ma = max(ma, S[j])
            abc1 = max(abc1, ma + A[i])
            abc2 = max(abc2, ma - A[i])
            S[i] = max(abs(A[i] - MI[de]), abs(MA[de] - A[i])) + ma
        for i in Y[de]:
            S[i] = max(S[i], abc1 - A[i], abc2 + A[i])
    print(S[0])
import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import deque
T = int(input())
for _ in range(T):
    N = int(input())
    X = [[] for i in range(N)]
    pp = [int(a) - 1 for a in input().split()]
    for (i, p) in enumerate(pp, 1):
        X[i].append(p)
        X[p].append(i)
    P = [-1] * N
    Q = deque([0])
    R = []
    while Q:
        i = deque.popleft(Q)
        R.append(i)
        for a in X[i]:
            if a != P[i]:
                P[a] = i
                X[a].remove(i)
                deque.append(Q, a)
    Y = [[0]]
    D = [0] * N
    for i in R[1:]:
        D[i] = D[P[i]] + 1
        while len(Y) <= D[i]:
            Y.append([])
        Y[D[i]].append(i)
    A = [0] + [int(a) for a in input().split()]
    d = max(D) + 1
    MI = [10 ** 9] * d
    MA = [0] * d
    for (i, a) in enumerate(A):
        MI[D[i]] = min(MI[D[i]], a)
        MA[D[i]] = max(MA[D[i]], a)
    S = [0] * N
    for i in Y[-1]:
        S[i] = max(abs(A[i] - MA[-1]), abs(A[i] - MI[-1]))
    for de in range(d - 1)[::-1]:
        abc1 = 0
        abc2 = -10 ** 9
        for i in Y[de]:
            ma = 0
            for j in X[i]:
                ma = max(ma, S[j])
            abc1 = max(abc1, ma + A[i])
            abc2 = max(abc2, ma - A[i])
            S[i] = max(abs(A[i] - MI[de]), abs(MA[de] - A[i])) + ma
        for i in Y[de]:
            S[i] = max(S[i], abc1 - A[i], abc2 + A[i])
    print(S[0])