给定一棵以 $$$1$$$ 为根、有 $$$n$$$ 个顶点的树,以及长度为 $$$n$$$ 的排列 $$$p$$$,由整数 $$$0, 1, \ldots, n - 1$$$ 组成,其中 $$$p_v$$$ 表示顶点 $$$v$$$ 的权重。
让 $$$S_v$$$ 表示写在属于从 $$$1$$$ 到 $$$v$$$ 的路径的顶点上的权重集。将函数 $$$f$$$ 定义为 $$$f(v) = \mathrm{MEX}(S_v)$$$,即由根和 $$$v$$$(含)之间的简单路径上的顶点权重组成的集合上的 $$$\mathrm{MEX}$$$,其中 $$$\operatorname{MEX}$$$ 是整数集合 $$$c_1, c_2,\ldots,c_k$$$被定义为集合$$$c$$$中不出现的最小非负整数$$$x$$$。
另外,给出以下操作:
- 选择一个整数 $$$v$$$ ($$$1 \leq v \leq n$$$) 并将 $$$f(v)$$$ 分配给 $$$p_v$$$。
执行上述操作后,您的目标是找到 $$$\sum\limits_{v = 1}^n f(v)$$$ 的最大值 不超过一次 (可能为零)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 树的顶点数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i \le n - 1$$$) — 数组 $$$p$$$ 的元素。保证从 $$$0$$$ 到 $$$n - 1$$$ 的每个整数在 $$$p$$$ 中只出现一次。
接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$),表示顶点 $$$x_i$$$ 和 $$$y_i$$$ 之间的一条边。保证这些边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一行包含一个整数:执行上述操作不超过一次后 $$$\sum\limits_{v = 1}^n f(v)$$$ 的最大值(可能为零)。
示例
输入复制
71031 0 21 21 361 4 5 2 0 31 41 56 22 52 351 2 3 0 41 22 33 44 5109 8 7 1 3 2 5 4 6 06 103 18 74 22 87 510 93 96 498 4 0 6 5 7 3 1 28 34 24 69 37 61 58 59 271 5 2 3 6 0 47 64 37 25 12 46 5
输出复制
14129302617
注意
在第一个示例中,不执行任何操作是最佳选择,因此答案是 $$$1$$$。
在第二个例子中,我们有
- $$$f(1) = \mathrm{MEX}(\{p_1\}) = \mathrm{MEX}(\{1\}) = 0$$$
- $$$f(2) = \mathrm{MEX}(\{p_1, p_2\}) = \mathrm{MEX}(\{1, 0\}) = 2$$$
- $$$f(3) = \mathrm{MEX}(\{p_1, p_3\}) = \mathrm{MEX}(\{1, 2\}) = 0$$$
我们有以下选择:
- 什么都不做会导致 $$$\sum\limits_{v = 1}^n f(v) = 2$$$
- 对顶点 $$$1$$$ 进行操作会将 $$$f(1) = 0$$$ 分配给 $$$p_1$$$,将 $$$f(1), f(2), f(3)$$$ 更改为 $$$1$$$,从而导致 $$$\sum\limits_{v = 1}^n f(v) = 3$$$
- 对顶点 $$$2$$$ 进行操作会将 $$$f(2) = 2$$$ 分配给 $$$p_2$$$,将 $$$f(2)$$$ 更改为 $$$0$$$,从而导致 $$$\sum\limits_{v = 1}^n f(v) = 0$$$
- 对顶点 $$$3$$$ 进行操作会将 $$$f(3) = 0$$$ 分配给 $$$p_3$$$,将 $$$f(3)$$$ 更改为 $$$2$$$,从而导致 $$$\sum\limits_{v = 1}^n f(v) = 4$$$
所以答案是$$$4$$$,通过对顶点$$$3$$$进行操作。