-
题目链接
-
题意
见题面
-
题解
-
前置知识
\(prufer\)序列
关于生成树的计数问题，我们又一个工具叫\(prufer\)序列，简单来说每一个生成树都与一个\(prufer\)序列一一对应，并且每一个点在\(prufer\)序中的出现次数为度数\(-1\)，这是最重要的性质，跟\(prufer\)序的构造方式有关，详细请自行学习。
-
解
根据\(prufer\)序，我们可以写出\(ans\)的式子：
\[ans=\sum \frac{(n-2)!}{\prod d_i!}\left(\prod_i (di+1)^m a^{d_i+1}\right)\left(\sum_i (di+1)^m\right) \]这个式子很不好求，我们将一些定量提出来，并将\(\frac{1}{\prod d_i!}\)放到里面，再推一推式子，就能化成：
\[ans=(n-2)!\prod a_i \sum \left(\sum_i\frac{(d_i+1)^{2m}}{d_i!}a_i^{d_i} \prod_{j\neq i} \frac{(d_j+1)^m}{d_i!} a_j^{d_i}\right) \]这时我们可以大胆猜测利用多项式，但发现\(a_i^{d_i}\)很不好搞，但是这个在多项式内和第\(i\)项的\(x\)的幂是一样的，可以合并，所以设
\[A(x)=\sum_i \frac{(i+1)^{2m}}{i!}x^i\\ B(x)=\sum_i \frac{(i+1)^{m}}{i!}x^i \]那么
\[ans=(n-2)!\prod a_i \sum \left(\sum_i A(a_ix)\prod_{j\neq i} B(a_jx)\right) \]将后面的连乘补全
\[ans=(n-2)!\prod a_i\sum\left(\sum_i \frac{A(a_ix)}{B(a_ix)}\right)\left(\prod_iB(a_jx)\right) \]所以我们要求的就是后面的式子。
求和可以直接做，连乘先\(ln\)再\(exp\)也能做。但是因为每一项都都带了一个\(a_i\)，所以我们现在的问题就是在求出\(\frac{A}{B}\)和\(\prod B\)后怎么把\(a_i\)变成系数。
设其中一个函数为\(F\)，第\(i\)次项系数为\(f_i\)，所以
\[\sum_iF(a_ix)=\sum_i\sum_jf_ja_i^jx^j=\sum_if_i\left(\sum_j a_j^i\right)x^i \]那么我们考虑对于每一个\(k\)，求出\(\sum_i a_i^k\)。
这有一个简单的方法，令这个的生成函数为\(G\)，那么
\[G(x)=\sum_i\sum_j a_i^jx^j=\sum_i\frac{1}{1-a_ix} \]求和不好做，但是如果是求积就可以分治\(fft\)，所以将求和转为求积，考虑\(ln\)，因为有分式，所以考虑\(ln\)后的求导。
那么很自然想到
\[(\ln(1-a_ix))'=-\frac{a_i}{1-a_ix}=\frac{1}{x}\left(1-\frac{1}{1-a_ix}\right) \]那么
\[\frac{1}{1-a_ix}=1-x(\ln(1-a_ix))' \]所以
\[G(x)=\sum_i\frac{1}{1-a_ix}=n-x\sum_i(\ln(1-a_ix))'=n-x\ln\left(\prod_i(1-a_ix)\right)' \]这样就可以直接分治\(fft\)，总复杂度\(O(nlog^2n)\)，瓶颈在两个分治\(fft\)。
其他的常数也挺大的
-