CF2219D MEX Replacement on Tree

给定一棵以 $1$ 为根、共有 $n$ 个结点的树，以及一个长度为 $n$ 的排列 $p$，其中包含整数 $0, 1, \ldots, n-1$，$p_v$ 表示结点 $v$ 的权值。 设 $S_v$ 表示从 $1$ 到 $v$ 的路径上的所有结点权值所组成的集合。定义函数 $f$，使得 $f(v) = \mathrm{MEX}(S_v)$，即从根到结点 $v$（包含 $v$）路径上的权值集合的 $\mathrm{MEX}$。其中，集合 $c_1, c_2, \ldots, c_k$ 的 $\operatorname{MEX}$ 表示所有未出现在集合 $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 \times 10^5$），表示树的结点个数。 第二行输入 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$0 \le p_i \le n - 1$），为数组 $p$ 的元素。保证 $0$ 到 $n-1$ 的每一个整数恰好出现一次。 接下来输入 $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)$ 的最大值。

在第一个样例中，不进行任何操作最优，因此答案为 $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$，总和变为 $3$ 3. 在结点 $2$ 上执行操作，将 $f(2) = 2$ 赋值给 $p_2$，则 $f(2)$ 变为 $0$，总和变为 $0$ 4. 在结点 $3$ 上执行操作，将 $f(3) = 0$ 赋值给 $p_3$，则 $f(3)$ 变为 $2$，总和变为 $4$ 因此答案为 $4$，在结点 $3$ 上执行操作。 由 ChatGPT 5 翻译