题解：CF1830D Mex Tree

· · 题解

考虑 \text{mex} 只可能有 0,1,2 三种，我们要让总答案尽可能大，就是尽可能让路径的 \text{mex} 为 2，也就是尽量让更多的路径都出现 0 和 1。容易想到贪心交替染色。但是交替染色的贪心是假的。可以被菊花连菊花的图卡掉，此时的最优解是两个菊花中心染 1 其余点染 0。

考虑正难则反。一条路径的 \text{mex} 不是 2 当且仅当这条路径上的点权全部一样。树上所有的路径数量是 \dfrac{n(n+1)}{2}，所有路径的答案都为 2 总答案就是 n(n+1)。一个大小为 k，颜色为 0 的连通块会让答案减少 \dfrac{i(i+1)}{2}，而一个大小为 k，颜色为 1 的连通块会让答案减少 i(i+1)。

考虑树形 dp。设 dp_{u,i,0/1} 代表点 u 的子树内，点 u 所在的连通块大小为 i，颜色为 0/1，答案最少要减少多少。

子树合并的时候转移就是：

dp_{u,i,0}=\min(dp_{u,i,0}+\min_{j=1}^{n}dp_{v,j,1},\min_{j=1}^{n}(dp_{u,j,0}+dp_{v,i-j,0}+i(i-j))\\ dp_{u,i,1}=\min(dp_{u,i,1}+\min_{j=1}^{n}dp_{v,j,0},\min_{j=1}^{n}(dp_{u,j,1}+dp_{v,i-j,1}+2\times i(i-j))

但是这样 dp 时空都是 O(n^2) 的，显然会爆炸。

考虑一个连通块太大肯定是不优的。我们可以回想交替染色的贪心。贪心不一定是最优的，所以我们的答案一定不会比贪心大（这里的答案指减去的部分）。

对于交替染色的贪心，所有长度大于 2 的路径的 \text{mex} 都是 2，而长度为 1 的路径，大概有 \dfrac{n}{2} 个点是 0，\text{mex} 是 1，剩下的 \dfrac{n}{2} 个点是 1，\text{mex} 是 0。所以减少的答案约是 n(n+1)-(\dfrac{n}{2}\times n(n-1)+\dfrac{n}{2})=\dfrac{3n}{2}。

对于一个大小为 i 的连通块，对于减少的答案的贡献是 i^2 级别的。因为答案一定不会大于贪心，所以 i^2\le \dfrac{3n}{2}，也就是 i\le \dfrac{\sqrt{6n}}{2}。所以我们找连通块上界只要到 \dfrac{\sqrt{6n}}{2} 就行了，时空变为 O(n\sqrt n)。

但是空间显然是开不下。

考虑到每个点的 dp 只需要用到子节点的 dp 值，所以一个点被用于求解父亲之后可以直接释放空间反复利用。

空间复杂度变为 O(n)。