← 返回题目列表

Codeforces · 1981/F

F. 海龟和树上的路径

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

请注意此问题中 $$$\text{MEX}$$$ 的不寻常定义。

Piggy 在 Turtle 生日那天给了 Turtle 一棵二叉树$$$^{\dagger}$$$,其中包含 $$$n$$$ 顶点和序列 $$$a_1, a_2, \ldots, a_n$$$。二叉树的根位于顶点$$$1$$$。

如果树中的一组路径 $$$P = \{(x_i, y_i)\}$$$ 恰好覆盖每条边一次,那么 Turtle 会认为这组路径是好的。请注意,一组好的路径可以覆盖一个顶点两次或更多次。

Turtle 将一组路径的值定义为 $$$\sum\limits_{(x, y) \in P} f(x, y)$$$,其中 $$$f(x, y)$$$ 表示所有 $$$a_u$$$ 的 $$$\text{MEX}^{\ddagger}$$$,使得顶点 $$$u$$$ 在简单路径上树中的 $$$x$$$ 到 $$$y$$$(包括起始顶点 $$$x$$$ 和结束顶点 $$$y$$$)。

Turtle 想知道所有好的路径集的最小值。请帮他算出答案!

$$$^{\dagger}$$$二叉树是每个非叶顶点最多有 $$$2$$$ 个儿子的树。

$$$^{\ddagger}\text{MEX}$$$ 整数集合 $$$c_1, c_2, \ldots, c_k$$$ 被定义为集合 $$$c$$$ 中不出现的最小正整数 $$$x$$$。例如,$$$[3, 3, 1, 4]$$$ 的 $$$\text{MEX}$$$ 为 $$$2$$$,$$$[2, 3]$$$ 的 $$$\text{MEX}$$$ 为 $$$1$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2.5 \cdot 10^4$$$) — 树中的顶点数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 序列 $$$a$$$ 的元素。

每个测试用例的第三行包含 $$$n - 1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i < i$$$) — 树中每个顶点的父节点。

对输入的附加约束:给定的树是二叉树,即每个非叶顶点最多有 $$$2$$$ 个儿子。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一个整数 - 所有良好路径集的最小值。

示例

输入 #1

5
5
3 2 2 1 1
1 1 2 2
5
3 2 1 1 1
1 1 2 2
6
1 2 1 2 1 3
1 2 3 3 4
7
2 1 2 3 1 2 1
1 1 2 2 3 3
10
1 2 2 1 4 2 3 1 2 1
1 1 2 2 3 3 4 5 5

输出 #1

4
6
6
6
7

注意

在第一个测试用例中,树如下所示。括号中的数字表示顶点的权重:

具有最小值的良好路径集是 $$$\{(2, 3), (4, 5)\}$$$。

请注意,在此测试用例中 $$$\{(4, 5)\}$$$ 和 $$$\{(3, 4), (4, 5)\}$$$ 不是好的路径集,因为每条边都应该被覆盖一次。

在第二个测试用例中,树如下:

具有最小值的好路径集合是$$$\{(1, 2), (1, 3), (4, 5)\}$$$。

在第三个测试用例中,树如下:

具有最小值的好路径集合为$$$\{(1, 6), (3, 5)\}$$$。