自动搬运

查看原文

来自洛谷，原作者为

	Aleph1022 「笑可以天然地飘洒 心是一地草野 唯一的家乡」

搬运于2025-08-24 22:44:51，当前版本为作者最后更新于2023-02-09 15:55:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

注意这个最大独立集不带权，因此我们可以贪心：如果儿子都不在最大独立集中就将父亲选入最大独立集中。
这样我们先记 $G, H$ 分别是根是否被选中的树的 OGF，借助 Polya Exp（$\operatorname{Exp}(F(x)) = \prod_{i\ge 1} \frac1{(1-x^i)^{f_i}} = \exp\left(\sum_{i\ge 1} \frac{F(x^i)}i\right)$）可以写出方程

$$\begin{cases} H = cx \operatorname{Exp}(G) \\ G = c \operatorname{Exp}(G+H) - c \operatorname{Exp}(G) \\ \end{cases} $$

考虑在线卷积维护 $\operatorname{Exp}(G)$ 和 $\operatorname{Exp}(G+H)$，借助 P5900 的手法即可解决。

接下来我们依然考虑重心为根即可，不过官方题解使用的是本质相同的 Otter's Formula，或许更为方便。以下直接给出结论，设答案为 $F$，有

$$F(x) = G(x) + H(x) - \frac12 G^2(x) + \frac12 G(x^2) - G(x) H(x) - \frac1{2x} H^2(x) + \frac1{2x} H(x^2) $$

写了个 $O(n\log^2 n/\log\log n)$，开 O2 后在洛谷上最慢的点不超过 1.2s。