CF1867F Most Different Tree 题解

zzzYheng · 2024-02-26 15:03:10 · 题解

题意：

给定一棵大小为 n 的有根树 G。

你要构造一棵大小也为 n 的有根树 G'，使得 G' 中存在最多的不与 G 中任何子树同构的子树。

数据范围：n \le 10^6。

思路：

重要观察：如果一个子树不与 G 中任何子树同构，那么所有包含其的子树都不会与 G 中的子树同构。

我得到这个观察的途径是考虑 \text{dp}，考虑子树合并的方式进行分步决策，容易发现如果其有一个儿子的子树不与任何 G 中子树同构，那么它也就不会与任何 G 中子树同构。

更进一步，我们一旦得到了一个不与 G 中任何子树同构的子树，就可以直接把剩下所有点依次拼接，作为其所有祖先。这样剩下的所有点的子树就都不会与 G 中的子树同构，一定是最优的。

所以现在的目标就是找到一个不与 G 中的任何子树同构的最小子树。

因为包含 k 个点的无标号有根树的个数是指数级别的，所以我们直接把前 n + 1 小的所有无标号有根树全搜出来，然后用树哈希暴力判断即可。

搜索的话考虑按树的大小从小到大搜。

假设这次搜大小为 k 的树，考虑把树分解为根和根的儿子的所有子树，问题等价于找出所有大小和为 k-1 的无标号子树集合，只需要保证编号不降即可保证不重不漏。

复杂度：\Theta(n\cdot f(n))，f(n) 是 n 个节点无标号有根树个数函数的反函数，不会超过 20，当然这个复杂度远远跑不满。