E. 移动与交换

每次测试的时间限制：$2$ 秒
内存限制：$256$ 兆字节

给定 $n-1$ 个整数 $a_2, \dots, a_n$，以及一棵以顶点 $1$ 为根的树，树有 $n$ 个顶点。所有叶子到根的距离相同，记为 $d$。

回忆：树是一个无环连通无向图。两个顶点之间的距离是它们之间简单路径上的边数。所有度数为 $1$ 的非根顶点称为叶子。如果顶点 $s$ 和 $f$ 之间有边相连，且 $f$ 到根的距离大于 $s$ 到根的距离，则称 $f$ 是 $s$ 的孩子。

初始时，红币和蓝币都在顶点 $1$ 上。设 $r$ 为红币所在顶点，$b$ 为蓝币所在顶点。你需要进行 $d$ 次移动。每次移动包含三个步骤：

1. 将红币移动到 $r$ 的任意一个孩子。
2. 将蓝币移动到任意一个顶点 $b'$，满足 $\text{dist}(1,b') = \text{dist}(1,b) + 1$。注意 $b$ 和 $b'$ 不一定有边直接相连。
3. 你可以选择交换两枚硬币（或者跳过这一步）。

注意，$r$ 和 $b$ 可以在任何时候相等，根上没有数字。

每次移动后，你获得 $|a_r - a_b|$ 分。问经过 $d$ 次移动后，你能获得的最大总分数是多少？

输入

第一行一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例数。

每个测试用例：

• 第一行一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）。
• 第二行包含 $n-1$ 个整数 $v_2, v_3, \dots, v_n$（$1 \le v_i \le n$，$v_i \neq i$）—— 第 $i$ 个表示顶点 $i$ 和 $v_i$ 之间有一条边。保证这些边构成一棵树。
• 第三行包含 $n-1$ 个整数 $a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 写在顶点上的数字。

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

输出

对于每个测试用例，输出一个整数：$d$ 次移动后能获得的最大分数。

示例

输入

4
14
1 1 1 2 3 4 4 5 5 6 7 8 8
2 3 7 7 6 9 5 9 7 3 6 6 5
6
1 2 2 3 4
32 78 69 5 41
15
1 15 1 10 4 9 11 2 4 1 8 6 10 11
62 13 12 43 39 65 42 86 25 38 19 19 43 62
15
11 2 7 6 9 8 10 1 1 1 5 3 15 2
50 19 30 35 9 45 13 24 8 44 16 26 10 40

输出

14
45
163
123

样例解释

在第一个测试用例中，一个最优方案是：

• 第 $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$。