CF1485E.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?

给你 $n - 1$ 个整数 $a_2, \dots, a_n$ 和一棵以顶点 $1$ 为根、含 $n$ 个顶点的树。所有叶子节点到根节点的距离均为 $d$。

回忆一下：树是一种无环的连通无向图。两个顶点之间的距离定义为它们之间唯一简单路径上的边数。所有非根且度数为 $1$ 的顶点均为叶子节点。若顶点 $s$ 与 $f$ 由一条边相连，且 $f$ 到根的距离大于 $s$ 到根的距离，则称 $f$ 是 $s$ 的一个子节点。

初始时，一枚红币和一枚蓝币均位于顶点 $1$ 上。设 $r$ 表示红币所在顶点，$b$ 表示蓝币所在顶点。你需要恰好执行 $d$ 次移动。每次移动包含以下三个步骤：

• 将红币移动至 $r$ 的任意一个子节点；
• 将蓝币移动至任意一个顶点 $b'$，使得 $dist(1, b') = dist(1, b) + 1$。其中 $dist(x, y)$ 表示 $x$ 与 $y$ 之间简单路径的长度。注意：$b$ 与 $b'$ 不一定由边直接相连；
• 你可以选择交换两枚硬币的位置（也可跳过此步）。

注意：在任意时刻，$r$ 和 $b$ 可以重合；且根节点上没有数字。

每次移动后，你将获得 $|a_r - a_b|$ 分。问：经过 $d$ 次移动后，最多能获得多少分？

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

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$）—— 表示树中顶点的数量。

每个测试用例的第二行包含 $n-1$ 个整数 $v_2, v_3, \dots, v_n$（$1 \leq v_i \leq n$，且 $v_i \neq i$）—— 其中第 $i$ 个数表示顶点 $i$ 与顶点 $v_i$ 之间存在一条边。保证这些边构成一棵树。

每个测试用例的第三行包含 $n-1$ 个整数 $a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$）—— 表示写在各顶点上的数字。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, print a single integer: the maximum number of points you can gain after $d$ moves.

对于每个测试用例，输出一个整数：经过 $d$ 步移动后你能获得的最大点数。

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

在第一个测试用例中，一个最优解为：

• 第 1 步：$r = 4$，$b = 2$；不交换；
• 第 2 步：$r = 7$，$b = 6$；交换（交换后 $r = 6$，$b = 7$）；
• 第 3 步：$r = 11$，$b = 9$；不交换。

总得分为 $|7 - 2| + |6 - 9| + |3 - 9| = 14$。

在第二个测试用例中，一个最优解为：

• 第 1 步：$r = 2$，$b = 2$；不交换；
• 第 2 步：$r = 3$，$b = 4$；不交换；
• 第 3 步：$r = 5$，$b = 6$；不交换。

总得分为 $|32 - 32| + |78 - 69| + |5 - 41| = 45$。