題目鏈接

CF方向
Luogu方向

題目解法

首先一個套路是普通冪轉(zhuǎn)下降冪（為什么？因為觀察到 $k$ 很小，下降冪可以轉(zhuǎn)化組合數(shù)問題，從而 $dp$ 求解）
即 $f(X{)}^k=\sum _{i=0}^k\{\genfrac{}{}{0ex}{}{k}{i}\}i!(\genfrac{}{}{0ex}{}{f(X)}{i})$
現(xiàn)在的問題是對于所有生成樹求出中間選 $i$ 條邊的方案數(shù)

我們令非空頂點的點集為關(guān)鍵點，其他生成樹上的點為包含點
考慮樹形 $dp$，令 $f_{i,j}$ 表示在 $i$ 的子樹中選出至少 $1$ 個關(guān)鍵點，且與 $i$ 連通的生成樹中選出 $j$ 條邊的方案數(shù)
考慮轉(zhuǎn)移：

1. $v$ 子樹中沒有關(guān)鍵點
   $f_{u,i}\to f_{u,i}$，不能計入答案計算，因為沒有改變關(guān)鍵點集合
2. 只有 $v$ 子樹中的關(guān)鍵點組成
   $f_{v,i}+f_{v,i?1}\to f_{u,i}$，不能計入答案計算，因為這個關(guān)鍵點集合在 $v$ 時已經(jīng)計算過
3. $u,v$ 子樹中均有關(guān)鍵點
   $f_{u,i}?f_{v,j}\to f_{u,i+j}\&f_{u,i+j+1}$，可以計入答案計算，因為改變了關(guān)鍵點集合

根據(jù)樹形 $dp$ 的時間復(fù)雜度計算，時間復(fù)雜度為 $O(nk)$

#include <bits/stdc++.h>
using namespace std;
const int N=100100,K=210,P=1e9+7;
int n,k,siz[N],s2[K][K],t[N],ans[N];
int ne[N<<1],e[N<<1],h[N],idx;
int f[N][K];
inline int read(){int FF=0,RR=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;return FF*RR;
}
inline void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
void dfs(int u,int fa){siz[u]=1,f[u][0]=1;for(int i=h[u];~i;i=ne[i]){int v=e[i];if(v==fa) continue;dfs(v,u);for(int j=0;j<=k;j++) t[j]=f[u][j];for(int j=0;j<=k;j++){inc(t[j],f[v][j]);if(j) inc(t[j],f[v][j-1]);}for(int p=0,mxp=min(k,siz[u]);p<=mxp;p++) for(int q=0,mxq=min(k-p,siz[v]);q<=mxq;q++){int coef=1ll*f[u][p]*f[v][q]%P;inc(t[p+q],coef),inc(t[p+q+1],coef);inc(ans[p+q],coef),inc(ans[p+q+1],coef);}siz[u]+=siz[v];for(int j=0;j<=k;j++) f[u][j]=t[j];}
}
int main(){n=read(),k=read();s2[0][0]=1;for(int i=1;i<=k;i++) for(int j=1;j<=i;j++) s2[i][j]=(s2[i-1][j-1]+1ll*s2[i-1][j]*j)%P;memset(h,-1,sizeof(h));for(int i=1;i<n;i++){int x=read(),y=read();add(x,y),add(y,x);}dfs(1,-1);int ANS=0;for(int i=1,fac=1;i<=k;i++,fac=1ll*fac*i%P) ANS=(ANS+1ll*ans[i]*s2[k][i]%P*fac)%P;printf("%d\n",ANS);return 0;
}