← 返回题目列表

Codeforces · 1485/E

E. 移动和交换

中文机器翻译题面 查看原题

给定您 $$$n - 1$$$ 整数 $$$a_2、\dots、a_n$$$ 和一棵具有 $$$n$$$ 顶点、以顶点 $$$1$$$ 为根的树。叶子与根的距离都是相同的$$$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$$$ 移动后您最多可以获得多少积分?

输入

第一行包含一个整数 $$$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$$$。

输出

对于每个测试用例,打印一个整数:$$$d$$$ 移动后可以获得的最大点数。

示例

输入 #1

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

输出 #1

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