模拟赛 28 题解

最小生成树+dp+思维

A 和 B 太水被吃了。

C.pair

把给定的条件看成边，那么答案就是最大生成基环树森林。

可以简单证明：一条边必须有一个点和它进行配对，所以点数 $\geqslant$ 边数。

那么用并查集维护就好了，再维护一下当前连通块是否包含环。

D.mex

好题。

首先考虑什么样的链会产生贡献，显然，它必须是连续的 $[0,k]$。

它会对什么产生贡献：$(u,v)$ 分别位于链两端的子树中。

并且我们发现贡献是递增的，也就是 $[0,k]$ 的mex是 $[0,k-1]$ 的mex加一。

所以我们考虑dp，设 $f[l][r]$ 表示当前链的端点是 $l,r$ 的贡献和。

转移利用刚才递增的特征，比 $f[l][son[r]]$ 和 $f[son[l]][r]$ 多了 $1$ 的贡献，而次数是左右两个 $siz$ 相乘。

其中 $son[u]$ 表示 $u$ 的出边中靠近链的那一个。

转移顺序不确定，采用记忆化搜索。