我们考虑 Burnside 引理。设 $X_k$ 是所有染 $k$ 个节点的方案，$G$ 是所有树同构意义下的置换群。我们要计算的是 $G$ 意义下，$X_k$ 中所有等价类的数量。由 Burnside 引理可知，这等于 $G$ 中每个置换下 $X_k$ 中不动点数量的平均值。

考虑对于每个特定的 $G$，如何计算 $G$ 的不动点数量。设在这个置换意义下，原树上有 $i$ 个点置换之后还是自身，其余 $n-i$ 个点置换之后不再是自身。那么可以发现，染色的 $k$ 个点只能在 $i$ 个不动的点中选择，总方案数为 $A_{i}^{k}=\dfrac{i!}{(i-k)!}$。这引导我们：如果我们能对每个 $i$，计算出有多少个置换恰能使得原树上有 $i$ 个节点不动，我们就能快速求出原题答案。

同官方题解中算法 4，我们以原树重心为根（方便起见假定树只有一个重心，两个重心的情况是类似的）。可以发现，$G$ 中所有置换等于每个节点同构子树的置换的乘积。我们记 $F_u(x)=\sum_{p=0}^{\mathrm{sz}(u)}f_{u,p}x^p$，其中 ${\mathrm{sz}(u)}$ 表示节点 $u$ 子树大小，$f_{u,p}$ 表示 $u$ 为根的子树中恰有 $p$ 个不动点的方案数。方便起见，称 $F_u(x)$ 是 $u$ 子树的生成函数。我们需要考虑计算一棵出现了 $k$ 次的、生成函数为 $F$ 的子树对答案的贡献 $\mathrm{calc}(F,k)$。

我们有

$$ \mathrm{calc}(F,k)=\sum_{i=0}^kF^i\binom{k}{i}D_{k-i}\mathrm{tot}(F)^{k-i} $$

其中 $D_i$ 是错排数，$\mathrm{tot}(F)$ 表示该子树中所有置换总数（即 $F(1)$ 的值）。组合意义：枚举有多少棵子树在这个置换中没有改变，设有 $i$ 棵，那么这 $i$ 棵树的生成函数是 $F^i$。同时，我们要考虑剩下 $k-i$ 棵树的方案数，显然这 $k-i$ 棵树构成了错排，同时要把这些树里的方案数全部乘进去。

计算 $\mathrm{calc}$ 可以类似官方题解中的分治 NTT 做到 $O(k\deg{F}(\log k\deg{F})\log k)$。最终对原问题的计算也可以参考官方题解轻重链剖分的做法，做到总复杂度 $O(n\log^3 n)$ 或者 $O(n\log^2 n)$。