Luogu5206 [WC2019] 数树

题意：对于两棵 个点的有标号无根树 ，定义 为 （边取交集）的连通块个数。

• 子任务一：给出 和常数 ，求 。
• 子任务二：给出 和常数 ，求 。
• 子任务三：给出 ，求 。

答案对 取模，，时限 。

---

子任务一（给出 ）

题意理解分，直接 std::map 送走。

子任务二（给出 ）

记 为两者边交集的大小，则 ，贡献形如 。

为了方便，我们忽略 并令 ，这样就把贡献改写成 。

也就是说，我们希望求出 套用子集反演可得： 其中 ，即在边集 的基础上继续连边，能得到的树的种类数。

• 定理： 将图连成了 个联通块，大小为 ，则继续连边的方案数是

证明：在 的基础上继续连边，可以视作将已有的联通快缩点，再建立一棵 个节点的树。若在联通块 之间连边，方案数为 ，记联通快的度数为 ，则连边方案数为 。

贡献和度数有关，考虑枚举全体 prufer 序列 ，则 。 后面的部分恰是多项式定理 ，即 。

---

代回原式： 注意其中的 （连通块个数）是和 对应的。

前面的系数按下不表，后面的意思是：令 ，大小为 的联通块乘积贡献是 ，求所有连通块贡献之积。

---

考虑 DP：

• 设 为 的子树中选取一个边的子集，和 连通的分量大小为 ，未计入，其余部分已计入的贡献和。

• 设 为 的子树中选取一个边的子集的贡献和。

加入分支 时，讨论选不选边 ，有转移： 这是个树上背包，子树大小剪枝可做到 ，无法通过。若要用 FFT 优化，复杂度可能是 或 且很难写。

事实上，状态可以缩减。注意到我们最后只取 作为答案，可以不维护整个。

把转移表示成幂级数，设 则有 （似乎更好懂了）

考虑加入一个分支 带来的变化。记旧的 为 。 因此，只需维护 和 就能转移。（最终我们只需要 ）

复杂度 。（听说这个 DP 有一个优美的组合意义）

子任务三（ 均任取）

接续子任务二的结论 其中 是由 生成的连通块大小。

该式的组合意义是 SET 变换，大小为 的的连通块权值是 ，多项式 exp 即可。复杂度 。