CF1097G Vladislav and a Great Legend解题报告：
题意
给定一个 (n) 个节点的树，定义 (f(S)) 为 (S) 的虚树边数，给定常数 (k)，求：
[sum_{Sin{1,2,cdots,n},S
evarnothing}f(S)^k
]
分析
考虑用斯特林数拆开 (k) 次幂：
[sum_{Sin{1,2,cdots,n},S
evarnothing}sum_{i=0}^negin{Bmatrix}k\iend{Bmatrix}{f(S)choose i}i!\=sum_{i=0}^negin{Bmatrix}k\iend{Bmatrix}i!sum_{Sin{1,2,cdots,n},S
evarnothing}{f(S)choose i}
]
考虑计算后面的贡献，可以考虑用树上背包来计算，这是平凡的。
代码
#include<stdio.h>
#include<vector>
using namespace std;
const int maxn=100005,maxk=205,mod=1000000007;
int n,k,ans;
int S[maxn][maxk],g[maxk],f[maxn][maxk],sz[maxn],fac[maxn],tot[maxn];
vector<int>v[maxn];
void dfs(int x,int last){
sz[x]=1,f[x][0]=2;
for(int i=0;i<v[x].size();i++)
if(v[x][i]!=last){
int y=v[x][i];
dfs(y,x);
for(int u=0;u<=sz[y]&&u<=k;u++)
tot[u]=(tot[u]-f[y][u]+mod)%mod;
for(int u=0;u<=sz[x]&&u<=k;u++)
for(int v=0;v<=sz[y]&&u+v<=k;v++)
g[u+v]=(g[u+v]+1ll*f[x][u]*f[y][v])%mod;
sz[x]+=sz[y];
for(int u=0;u<=k;u++)
f[x][u]=g[u],g[u]=0;
}
for(int i=0;i<=k;i++)
tot[i]=(tot[i]+f[x][i])%mod;
for(int i=k;i>=1;i--)
f[x][i]=(f[x][i]+f[x][i-1])%mod;
f[x][1]=(f[x][1]-1+mod)%mod;
}
int main(){
scanf("%d%d",&n,&k);
fac[0]=fac[1]=S[1][1]=1;
for(int i=2;i<=k;i++){
fac[i]=1ll*fac[i-1]*i%mod;
for(int j=1;j<=k;j++)
S[i][j]=(S[i-1][j-1]+1ll*j*S[i-1][j])%mod;
}
for(int i=1,x,y;i<n;i++)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
dfs(1,0);
for(int i=0;i<=k;i++)
ans=(ans+1ll*S[k][i]*fac[i]%mod*tot[i])%mod;
printf("%d
",ans);
return 0;
}