简要题意.

给定 $l, r, c$，计数最大独立集大小在 $[l, r]$ 内，各个点具有 $c$ 种可能的颜色的无标号无根树个数。

$r \le 5 \times 10^5$，时限巨大。

注意这个最大独立集不带权，因此我们可以贪心：如果儿子都不在最大独立集中就将父亲选入最大独立集中。这样我们先记 $G, H$ 分别是根是否被选中的树的 OGF，借助 Polya Exp 可以写出方程

$$ \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)$，借助洛谷 5900 的手法即可解决。

接下来我们依然考虑重心为根即可，不过题解使用的是本质相同的 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) $$

时限是 45s，我写了个 $O(r\log^2 r/\log\log r)$ 获得了 899ms 的好成绩。