首先我们明确一下暴力 $O(nm^2)$ 或 $O(nm\log m)$ 是怎么做的。
考虑最大独立集的一种算法：对于点权 $a_u$，求出序列 $b_u = \max\left(a_u - \sum_v b_v, 0\right)$，然后 $\sum_u b_u$ 就是答案。
于是立刻有暴力 DP $f(u, k)$ 表示 $b_u=k$ 的方案数。转移时，我们首先将儿子的第二维卷积，并做一次前缀和得到数列 $t_k$，然后有（其中 $s_u$ 表示 $u$ 的子树大小）
$$f(u, k) = \begin{cases}m^{s_u} - \sum_{j=0}^{m-1} t_j, & k=0 \\ t_{m-k}, & 1\le k \le m\end{cases}$$
接下来考虑用 GF 来表达这个 DP。
我们容易验证以上转移等效于任取 $a_u=1,\dots,m$ 之后变换 $b_u = \max\left(a_u - \sum_v b_v, 0\right)$。
接下来我们注意到转移的时候儿子处只关心 $k=0,\dots,m-1$ 的值，因此我们考虑 $f(u, k)$ 的一个截断的 GF $f_u(x) = \sum_{k=0}^{m-1} f(u, k) x^k$。
可以归纳证明，存在多项式 $g_u(x), h_u(x)$ 满足 $\deg g_u(x), \deg h_u(x) \le s_u$ 且
$$ f_u(x) = \frac{g_u(x)}{(1-x)^{s_u}} \bmod x^m = \frac{g_u(x)+x^m h_u(x)}{(1-x)^{s_u}} $$
转移时，我们首先考虑 $p(x) = \prod_v g_v(x)$ 满足 $\deg p(x) < s_u$，然后容易算出
$$ \sum_{k=0}^{m-1} t_k = \sum_{k=0}^{m-1} [x^k] \frac{p(x)}{(1-x)^{s_u-1+1}} = [x^{m-1}] \frac{p(x)}{(1-x)^{s_u+1}} $$
接下来，为了取模 $x^m$，我们需要算出 $q(x)$ 满足
$$ \frac{p(x)}{(1-x)^{s_u}} \bmod x^m = \frac{p(x)+x^m q(x)}{(1-x)^{s_u}} $$
提取 $[x^{m+k}]$ 可得
$$ [x^k] \frac{q(x)}{(1-x)^{s_u}} = -[x^{m+k}] \frac{p(x)}{(1-x)^{s_u}} $$
同时容易证明 $\deg q(x) < s_u$，因此我们只需要对于 $k=0,\dots,s_u-1$ 算出 $[x^{m+k}] \frac{p(x)}{(1-x)^{s_u}}$ 后，再卷上 $(1-x)^{s_u}$ 即可得到 $q(x)$。前者提取系数同样可得卷积。
记 $\Delta=m^{s_u}-\sum_{k=0}^{m-1} t_k$，最后我们需要翻转系数并加 $\Delta$，可以得到
$$ \begin{aligned} \sum_{k=0}^m f(u, k) x^k &= \frac{x^m \left(p(x^{-1})+x^{-m} q(x^{-1})\right)}{(1-x^{-1})^{s_u}} + \Delta \\ &= \frac{(-1)^{s_u} \left(x^{m+s_u} p(x^{-1}) + x^{s_u} q(x^{-1}) \right) + \Delta \cdot (1-x)^{s_u}}{(1-x)^{s_u}} \end{aligned} $$
注意这里是 $f(u, k)$ 未截断的 GF。
于是我们取 $f_u(x) = (-x)^{s_u} q(x^{-1}) + \Delta \cdot (1-x)^{s_u}$ 即可。同时在答案中累计
$$ \begin{aligned} &\quad\, \sum_{k=1}^m m^{n-s_u} \cdot k \cdot f(u, k) \\ &= \sum_{k=1}^m m^{n-s_u} \cdot k \cdot [x^k] \frac{f_u(x)}{(1-x)^{s_u}} \\ &= m^{n-s_u} [x^{m-1}] \frac1{1-x}\left(\frac{f_u(x)}{(1-x)^{s_u}}\right)' \\ &= m^{n-s_u} [x^{m-1}] \left(\frac{f_u'(x)}{(1-x)^{s_u+1}}-\frac{s_u f_u(x)}{(1-x)^{s_u+2}}\right) \end{aligned} $$
时间复杂度 $O(n^2 \log n)$。