CF1485E Move and Swap

现给定 $n - 1$ 个整数 $a_2, \dots, a_n$ 和一棵有 $n$ 个节点并且以节点 $1$ 为根的有根树。树中所有的叶子结点到根的距离都相等，为定值 $d$。 我们定义一棵树是一个没有环的连通无向图。两个节点间的距离定义为它们间的简单路上的边的数量之和。除了根节点外，其他度为 $1$ 的节点都是叶子结点。对于任意节点 $s$ 和 $f$，如果节点 $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_1$）。 每次移动完成，你将得到 $|a_r - a_b|$ 的分数。进行 $d$ 次移动后，你能得到的最大分数和是多少？

第一行包含一个整数 $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$（$2 \leq i \leq n$）个整数表示节点 $i$ 与 $v_i$ 之间有边相连。数据保证能构成一棵树。 每组测试点的第三行包含 $n-1$ 个整数 $a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），其中 $a_i$ 表示节点 $i$ 上的数字。 数据保证所有 $t$ 组测试数据的 $n$ 的和不超过 $2 \cdot 10^5$。

$t$ 行，每行一个整数表示对应测试点的答案，即进行 $d$ 次移动后能得到的最大分数。

第一组测试中，最优解为： - 第 $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$。