自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 22:23:52，当前版本为作者最后更新于2020-08-20 22:44:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

（摘自 NOI 2020 翻盘记）

本人赛时 AC，但是没拷代码，先写一下解法，有空补代码，填补一下题解的空白。

讲题主要讲了合并的思路，但是我用的是分治的思路。

观察 $1$：如果一棵树每个点的左右儿子 size 的 $\min$ 不超过 $1$，那么称为好树，则一旦仅有有限多个好树不在 $\operatorname{grow}(\mathcal{T})$ 中，那么树林 $\mathcal{T}$ 便是几乎完备的。

证明非常简单，因为任何一棵树 $T$ 可以由深度相等的一棵好树长出，所以只要一定深度以上的好树都能被生成，那么这个深度以上的所有树都能被生成。

观察 $2$：如果输入的一棵树不是好树，那么它便无用。

证明：非不能长出好树，所以它对长出好树没有任何帮助，根据观察 $1$，我们只关心好树能否被长出，它自然就无用了。

这告诉我们，如果只保留有效的树，那么对于每一个结点，向下递归不可能同时递归左右子树，因为至少有一个是大小不超过 $1$ 的平凡情况。

因此递归可以考虑，设 $solve(\mathcal{T})$ 表示判定树林 $\mathcal{T}$ 是否几乎完备，将其中的树分成四类：

1. 根只有左儿子；

2. 根只有右儿子；

3. 根有左右儿子且左儿子大小为 $1$；

4. 根有左右儿子且右儿子大小为 $1$；

（3.4 可能有唯一交集，但问题不大）

对于 $1,2$，直接递归其左/右儿子即可。

对于 $3,4$，对应递归相反方向（即较大的一边）的儿子即可。

如果四种情况全部几乎完备，则原树林几乎完备；特殊地，如果 $\mathcal{T}$ 中存在单点，则直接返回几乎完备。

考虑证明上面断言的正确性：

所有可能的好树仅有上面四种，并且分别可以利用上面说的四种情况的树生成，所以只要四种树都分别几乎完备，则原树林几乎完备；反之如果有一种树不几乎完备，那么就可以构造无穷多的反例。

由于每个树最多被递归深度次，根据讲课时讲师的分析，在卡满情况下深度仅能到达 $O(\sqrt n)$，那估计复杂度是线性的了。