Aly_

​ 关于本题的各种做法...

第一步

​ 首先，如果一个大小为 $a_i$ 的连通块连出了 $d_i$ 条边，那么这 $d_i$ 条边在连通块内部的出发点就总共有 $a_i^{d_i}$ 种组合，即，这会对答案产生 $a_i^{d_i}$ 的贡献。于是，对于一种所有点的度数分别为 $d_1,\cdots,d_n$ 的情况，它们对答案的贡献就是 $\prod_i a_i^{d_i}d_i^m(\sum_id_i^m)$。

​ 考虑使图的生成树和 Prufer 序列一一对应。对于一个度数为 $d_i$ 的连通块（以下简称 “ 点 ”）$i$，其在 Prufer 序列中会出现 $d_i-1$ 次。我们现在尝试把一个个点填入 Prufer 序列。

​ 设 $f_{i,j}$ 表示当前已经把前 $i$ 个点填入了 Prufer 序列，占了 $j$ 个位置的 $\prod_i a_i^{d_i}d_i^m$ 总和，$g_{i,j}$ 表示对应情况下的 $\prod_i a_i^{d_i}d_i^m(\sum_id_i^m)$ 总和。枚举第 $i$ 个点占了多少个位置，容易得出：

$f_{i,j}=\sum_{k\leq j}f_{i-1,k}\dbinom{j}{k}a_i^{j-k+1}(j-k+1)^m$

$g_{i,j}=\sum_{k\leq j}g_{i-1,k}\dbinom{j}{k}a_i^{j-k+1}(j-k+1)^m+\sum_{k\leq j}f_{i-1,k}\dbinom{j}{k}a_i^{j-k+1}(j-k+1)^{2m}$

​ 得到一个 $O(n^3)$ 的暴力。

​ 以后的讨论都以此为基础。

第二步

​ 发现 $f_{i,j}$ 可以卷积地转移。

​ 使用指数生成函数，记 $F_i(x)=\sum_j\dfrac{f_{i,j}}{j!}x^j$，$G_i(x)$ 类似，我们把上述转移改写成如下形式：

$F_i(x)=F_{i-1}(x)*P_i(x)$

$G_i(x)=G_{i-1}(x)*P_i(x)+F_{i-1}(x)*Q_i(x)$

​ （虽然相当不严谨，若无特殊需要这里不再区分多项式 $F(x)$ 和 $F$。）

​ 其中

$P_i(x)=\sum_j\frac{a_i^{j+1}(j+1)^m}{j!}x_j$

$Q_i(x)=\sum_j\frac{a_i^{j+1}(j+1)^{2m}}{j!}x_j$

​ （$P_i$ 和 $Q_i$ 长得这么像？）

​ 进一步地，可以用矩阵改写成如下形式

$\begin{pmatrix} P_i & 0\\ Q_i & P_i \end{pmatrix}* \begin{pmatrix} F_{i-1}\\ G_{i-1} \end{pmatrix}= \begin{pmatrix} F_i\\ G_i \end{pmatrix}$

​ 于是只要求 $\prod_i\begin{pmatrix}P_i & 0\\Q_i & P_i\end{pmatrix}$ 即可。

​ 再化 $P_i$，有

$P_i(x)=\sum_j\frac{a_i^{j+1}(j+1)^m}{j!}x_j\\ =\sum_j\frac{a_i^{j+1}}{j!}x^j\sum_{k\leq m}\begin{Bmatrix}m\\k\end{Bmatrix}\dbinom{j+1}{k}k!\\ =\sum_{k\leq m}\begin{Bmatrix}m\\k\end{Bmatrix}k!\sum_j\frac{a_i^{j+1}(j+1)}{(j+1-k)!}x^j\\$

​ 前面的先不管，看到后面的和式有点像 exp 的形式。具体地，若它真的有一个类似形式的话，$(j+1)$ 意味着可能需要求导，下面的阶乘平移了 $k$ 意味着需要多项式平移，而上面的 $a_i^{j+1}$ 意味着有类似 $e^{a_ix}$ 的式子出现。

​ 综合上面几点不难得出后面和式就是

$(a_i^kx^ke^{a_ix})' =a_i^kx^{k-1}(k+a_ix)e^{a_ix}$

​ 继续化

$P_i(x)=\sum_{k\leq m}\begin{Bmatrix}m\\k\end{Bmatrix}k!a_i^kx^{k-1}(k+a_ix)e^{a_ix}\\ =e^{a_ix}\sum_{k\leq m}\begin{Bmatrix}m+1\\k+1\end{Bmatrix}a_i^{k+1}x^k$

​ 最后一步用到了 $\begin{Bmatrix}m\\k\end{Bmatrix}=k\begin{Bmatrix}m-1\\k\end{Bmatrix}+\begin{Bmatrix}m-1\\k-1\end{Bmatrix}$。对 $Q_i$ 的推导同理。

​ 再记 $A_i(x)=\sum_{k\leq m}\begin{Bmatrix}m+1\\k+1\end{Bmatrix}a_i^{k+1}x^k,B_i(x)=\sum_{k\leq 2m}\begin{Bmatrix}2m+1\\k+1\end{Bmatrix}a_i^{k+1}x^k$。

​ 注意到 $A_i,B_i$ 都是次数小于等于 $2m$ 的多项式。

​ 回头看原来的矩阵乘积，把所有 exp 提出来，得到所求的式子为

$e^{Sx}\prod_i\begin{pmatrix}A_i & 0\\B_i & A_i\end{pmatrix}$

​ FFT 分治。复杂度 $O(nm\log^2 n)$（精细的实现可以有 $O(nm\log n\log m)$？）。

​ 注意的是，直接做矩阵乘法的常数显然巨大，但这个矩阵的特殊形式有

$\begin{pmatrix}A_i & 0\\B_i & A_i\end{pmatrix}\begin{pmatrix}A_j & 0\\B_j & A_j\end{pmatrix}=\begin{pmatrix}A_iA_j & 0\\B_iA_j+A_iB_j & A_iA_j\end{pmatrix}$

​ 前后形式相同，可以很方便地转移。可以通过本题。

​ 继续优化？

第三步

​ 上面的小优化可以推广。可以归纳地证明所有这些矩阵乘起来后左下角多项式为

$\sum_iB_i\prod_{j\ne i}A_j=\prod_iA_i(\sum_jB_j*A_j^{-1})$

​ 设 $\{a_j\}$ 幂和的生成函数 $T(x)=\sum_i(\sum_ja_j^i)x^i$。

​ 注意到 $A_i(x)$ 的形式都很接近。设 $A(x)=\sum_{k\leq m}\begin{Bmatrix}m+1\\k+1\end{Bmatrix}x^k$，那么 $A_i(x)=a_iA(a_ix)$。 $B_i(x)$ 同理。

​ 然后

$\sum_j{B_j}*{A_j}^{-1}=\sum_j{B(a_jx)}*{A(a_jx)}^{-1}=\sum_j(B*A^{-1})(a_jx)=T\cdot(B*A^{-1})$

​ 这里 $\cdot$ 是点乘，即对应位置相乘。

​ 继续

$\prod_i A_i=\exp \sum_i \ln A_i=\exp \sum_i \ln a_iA(a_ix)=\exp(T\cdot\ln A)$

​ 如果求出 $T$ 的话，这两个式子都可以快速求解。求 $T$ 是一个经典问题，有

$T(x)=\sum_i(\sum_ja_j^i)x^i=\sum_j\sum_i (a_jx)^i=\sum_j\frac{1}{1-a_jx}=\frac{\sum_i\prod_{j\ne i}(1-a_jx)}{\prod_i(1-a_ix)}$

​ FFT 分治解决，复杂度 $O(n\log^2 n)$，这里不再赘述。

​ 最后放出原问题完整的求解式（似乎两个 exp​ 可以合并？）：

$Ans=(n-2)![x^{n-2}]\exp(Sx)*(T\cdot(B*A^{-1}))*\exp(T\cdot\ln A)$

​ 于是最终我们在 $O(n\log^2 n)$ 的时间内解决了问题。

​ 因为是多项式题，本蒟蒻代码较长而且码风奇丑，就不放代码了。