题解 P6776 【[NOI2020]超现实树】

· · 题解

（摘自 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)，那估计复杂度是线性的了。