PA 2021 5A
Aleph1022
·
·
题解
注意这个最大独立集不带权，因此我们可以贪心：如果儿子都不在最大独立集中就将父亲选入最大独立集中。
这样我们先记 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。