分析
一类树（连出的边数集合一定）的贡献
\[ \mathbb{Ans}(\{d_n\}|\sum_id_i=2(n-1))=\prod_ia_i^{d_i}\prod_id_i^m\sum_{i}d_i^m \]
引入Prufer序列，设\(d_i\)为点（联通块）在序列中出现的次数，转换
\[ \begin{aligned} \mathbb{Ans}(\{d_n\}|\sum_{i}d_i=n-2) &=\prod_ia_i^{d_i+1}\prod_i{(d_i+1)^m}\sum_{i}(d_i+1)^m\\ &=\prod_ia_i^{d_i+1}(d_i+1)^m\sum_{i}(d_i+1)^m\\ \end{aligned} \]
那么枚举所有的Prufer的组合，总答案
\[ \begin{aligned} \mathbb{Ans} &=\sum_{\sum_id_i=n-2}\frac{(n-2)!}{\prod_id_i!}\prod_ia_i^{d_i+1}(d_i+1)^m\sum_{i}(d_i+1)^m\\ &=(n-2)!\prod_ia_i\sum_{\sum_id_i=n-2}\prod_i\frac{a_i^{d_i}(d_i+1)^m}{d_i!}\sum_i(d_i+1)^{m}\\ &=(n-2)!\prod_ia_i(\sum_{\sum_id_i=n-2}\sum_i\frac{a_i^{d_i}(d_i+1)^{2m}}{d_i!}\prod_{i\not=j}\frac{a_j^{d_i}(d_j+1)^m}{a_j!}) \end{aligned} \]
G8麻烦……请出生成函数
\[ A(x)=\sum_i\frac{x^i(i+1)^{2m}}{i!}\\ B(x)=\sum_i\frac{x^i(i+1)^m}{i!}\\ F(x)=\sum_iA(a_ix)\prod_{i\not=j}B(a_jx) \]
注意到\([n-2]F(x)\)正是\(\mathbb{Ans}\)中非常数部分（括号注明部分）。于是需要处理\(F(x)\)
\[ F(x)=\sum_i\frac{A(a_ix)}{B(a_ix)}\prod_{i}B(a_ix)=\sum_i\frac{A(a_ix)}{B(a_ix)}\exp(\sum_{i}\ln(B(a_ix))) \]
在\(\ln\exp\)中视\(a_ix\)整体为变量，处理\(\frac{A(x)}{B(x)}\)和\(\ln(B(x))\)的系数，再用\(a_ix\)代换\(x\)，求出\(\sum\frac{A(a_ix)}{B(a_ix)}\)以及\(\sum\ln(B(a_ix))\)。
这两个过程本质相同：和函数\(\sum\)的第\(i\)向系数是单个函数的\(i\)项系数（常量）乘上\(\sum_ka_k^i\)。
于是涉及到一个序列的幂和，它的生成函数
\[ f(x)=\sum_i\sum_ja_j^ix^i=\sum_i\sum_j(a_ix)^j=\sum_i\frac{1}{1-a_ix}\\ g(x)=\sum_i\ln(\frac{1}{1-a_ix})=\sum_i\frac{-a_i}{1-a_ix}=-\sum_i\sum_ja_i^{j+1}x^j\\ f(x)=n-x\times g(x)\\ g(x)=\sum_i\ln((1-a_ix)^{-1})=-\ln(\prod_i1-a_ix) \]
关于这个\(\ln\)视\(x\)为变量而非\(a_ix\)，于是分治FFT处理\(g(x)\)，设\(L\)为不小于\(n\)的2的幂，可以粗略的估计为复杂度
\[ \sum_d^{\log L}\frac{L}dd\log d=L\sum_d^{\log L}\log d=L\log(\log(L)!) \]
打表发现\(\log(\log(L)!)\)较\(\log(L)\)略大，远小于\(\log^2\)所在规模，于是近似认为复杂度为\(O(n\log n)\)
最后慢慢推回去……
实现
有很多波折……目前洛谷rank1
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200000;
const int MOD=998244353;
inline int qpow(int x,int y) {
int c=1;
for(; y; y>>=1,x=(ll)x*x%MOD) if(y&1) c=(ll)c*x%MOD;
return c;
}
//------- POLYNOMIAL BEGIN -------
int w[N],rev[N],_inv[N],lmt;
inline void preDone(int len) {
int l=0; lmt=1; _inv[1]=1;
while(lmt<=len) lmt<<=1,l++;
for(int i=0; i<lmt; ++i) {
rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
if(i>1) _inv[i]=(ll)_inv[MOD%i]*(MOD-MOD/i)%MOD;
}
int wlmt=qpow(3,(MOD-1)>>l),tmp=lmt>>1; w[tmp]=1;
for(int i=tmp+1; i<lmt; ++i) w[i]=(ll)w[i-1]*wlmt%MOD;
for(int i=tmp-1; i>0; --i) w[i]=w[i<<1];
lmt=l;
}
inline void DFT(int a[],int len) {
static unsigned long long tmp[N];
int u=lmt-__builtin_ctz(len),T;
for(int i=0; i<len; ++i) tmp[rev[i]>>u]=a[i];
for(int m=1; m<len; m<<=1)
for(int i=0,s=m<<1; i<len; i+=s)
for(int j=0; j<m; ++j)
T=tmp[i+j+m]*w[m+j]%MOD,tmp[i+j+m]=tmp[i+j]+MOD-T,tmp[i+j]+=T;
for(int i=0; i<len; ++i) a[i]=tmp[i]%MOD;
}
inline void IDFT(int a[],int len) {
reverse(a+1,a+len); DFT(a,len);
ll T=MOD-(MOD-1)/len;
for(int i=0; i<len; ++i) a[i]=T*a[i]%MOD;
}
inline int getLen(int len) {
return 1<<(32-__builtin_clz(len));
}
inline void getDer(int a[],int b[],int n) {
for(int i=0; i&l