给定您 $$$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$$$。