题解：CF762F Tree nesting

· · 题解

注意到 |T| 很小，直接把 T 中所有本质不同的有根连通子图跑出来，树哈希要换根 DP，复杂度是 \mathcal O(m2^m) 的；然后设 f_{u,i} 表示 S 中选了一个最高点为 u 的连通块，对应第 i 种子图，转移时枚举两种子图，判定拼起来之后是否合法，容易用树哈希做到 \mathcal O(nC(m)^2)，其中 C(m) 为 m 个点的树的有根连通子图的最大种类数。

考虑进一步分析复杂度，首先一棵子图被劈成两半的方案数是 \mathcal O(m) 的，因此可能有效的转移对只有 \mathcal O(mC(m)) 种，预先处理出合法的转移，复杂度为 \mathcal O(m2^m+nmC(m))，实现不好的话会带一个 \mathcal O(C(m)^2)。下面分析 C 的级别。

定义 n 阶斐波那契树 T_n 是一棵二叉树，左右子树分别为 T_{n-1} 和 T_{n-2}，边界条件 T_1 为单点，T_2 为单边。有 |T_n|=|T_{n-1}|+|T_{n-2}|+1\approx A\phi^n，C(T_n)=(C(T_{n-1})+1)(C(T_{n-2})+1)\approx\exp(B\phi^n)，数值计算 e^{B/A} 可以解得这种构造的 C(m)\approx\mathcal O(1.50^m)，感觉上这是最优的下界；但前面的 2^m 枚举所有连通点集拉完了，不过把直接枚举点集改成搜索扩展之后，这两部分不太能同时跑满。总之复杂度大概是 \mathcal O(m2^m+1.50^mnm) 的，感觉 m 可以开到 20 啊。

似乎有一个更高手的做法，考虑第一篇题解的做法，状压 T 中 v 的儿子有哪些被匹配了，但发现叶节点可以直接算掉，只用状压那些度数 >1 的儿子，这样的儿子个数一定不超过 \dfrac m2，因此这样复杂度就是 \mathcal O(2^{m/2}n\operatorname{poly}m) 的，\sqrt 2<1.50 所以复杂度更优秀，不过好像非常难写，而且跑的比较满。

其实如果你愿意的话可以把子树大小为 2 的儿子也算掉，复杂度大概是 \mathcal O(2^{m/3}n\operatorname{poly}m)，很逆天啊，不过这个 \operatorname{poly}m 好像得有 m^3 甚至更多。

不过一开始那个东西可以做对每种本质不同的树都计数，复杂度大概在 \mathcal O(nmT(m))，其中 T(m)\approx\widetilde{\mathcal O}(2.96^m) 为 m 个点的无标号有根树个数。

好像平衡规划一下可以做到 \mathcal O(2.95^{\frac{m}{\log m}}n\operatorname{poly}m)，真的假的。不过要是真的也肯定 non-practical 了。