← 返回题目列表

Codeforces · 2219/D

D. 树上的 MEX 替换

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

给定一棵以 $$$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)$$$ 的最大值(可能为零)。

示例

输入
复制

7
1
0
3
1 0 2
1 2
1 3
6
1 4 5 2 0 3
1 4
1 5
6 2
2 5
2 3
5
1 2 3 0 4
1 2
2 3
3 4
4 5
10
9 8 7 1 3 2 5 4 6 0
6 10
3 1
8 7
4 2
2 8
7 5
10 9
3 9
6 4
9
8 4 0 6 5 7 3 1 2
8 3
4 2
4 6
9 3
7 6
1 5
8 5
9 2
7
1 5 2 3 6 0 4
7 6
4 3
7 2
5 1
2 4
6 5

输出
复制

1
4
12
9
30
26
17

注意

在第一个示例中,不执行任何操作是最佳选择,因此答案是 $$$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$$$

我们有以下选择:

  1. 什么都不做会导致 $$$\sum\limits_{v = 1}^n f(v) = 2$$$
  2. 对顶点 $$$1$$$ 进行操作会将 $$$f(1) = 0$$$ 分配给 $$$p_1$$$,将 $$$f(1), f(2), f(3)$$$ 更改为 $$$1$$$,从而导致 $$$\sum\limits_{v = 1}^n f(v) = 3$$$
  3. 对顶点 $$$2$$$ 进行操作会将 $$$f(2) = 2$$$ 分配给 $$$p_2$$$,将 $$$f(2)$$$ 更改为 $$$0$$$,从而导致 $$$\sum\limits_{v = 1}^n f(v) = 0$$$
  4. 对顶点 $$$3$$$ 进行操作会将 $$$f(3) = 0$$$ 分配给 $$$p_3$$$,将 $$$f(3)$$$ 更改为 $$$2$$$,从而导致 $$$\sum\limits_{v = 1}^n f(v) = 4$$$

所以答案是$$$4$$$,通过对顶点$$$3$$$进行操作。