CF1830D Mex Tree 题解

因为 $01$ 序列的 $\text{mex}$ 值只有 $0,1,2$ 三种不同取值，所以考虑然后 dp：设 $f_{i,j,0/1}$ 表示当前处理了 $i$ 点为根的子树内的信息，$i$ 所对应的同色连通块的大小为 $j$，$i$ 点写的数字是 $0/1$，答案最少减少了多少。那么显然有下面的转移：

• $f_{u,i,0}\leftarrow \min(f_{v,j,1}+f_{u,i,0},f_{v,i-j,0}+f_{u,j,0}+ij-i^2)$
• $f_{u,i,1}\leftarrow \min(f_{v,j,0}+f_{u,i,1},f_{v,i-j,1}+f_{u,j,1}+2(ij-i^2))$

直接转移看上去时间复杂度为 $O(n^3)$，但可以考虑这样的一个策略：直接对树做黑白染色，容易证明该贪心策略答案减少的数量即为 $n+\sum\limits_{i=1}^n[col_i=1]\le 2n$ 也就是 $O(n)$ 级别的，而 dp 转移过程中枚举的同色连通块大小 $j$ 对答案的减小是 $O(j^2)$ 级别的，因此枚举的连通块大小只需要到 $O(\sqrt n)$ 级别即可。

剩下部分的转移其实可以看作是一个树上背包的形式，枚举连通块大小只枚举到子树大小即可保证时间复杂度为 $O(n\sqrt n)$，可以通过该题。