P4827 [国家集训队] Crash 的文明世界
由
[m^n=sum_{i=0}^{m}egin{Bmatrix}n\iend{Bmatrix}i!inom{m}{i}
]
得
[S(u)=sum_{i=1}^{n}operatorname{dis}(u,i)^k\
=sum_{i=1}^{n}sum_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix}j!inom{operatorname{dis}(u,i)}{j}\
=sum_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix}j!sum_{i=1}^{n}inom{operatorname{dis}(u,i)}{j}
]
瓶颈就是后面那个组合数了。
总感觉可以直接换根啊。搞半天才发现，组合数不裂开你就裂开了/fad
令 (f_{u,j}) 表示以 (u) 为根的子树内，(sum_{vin subtree(u)}dbinom{operatorname{dis}(u,v)}{j})
因为
[suminom{d}{j}=suminom{d-1}{j-1}+inom{d-1}{j}
]
所以
[f_{u,j}=sum_{vin son(u)} f_{v,j-1}+f_{v,j}
]
看到式子都能理解了吧，就是自己想要想好久。利用好距离差 (1) 这个条件。
这样以 (1) 为根就可以算了。
然后考虑换根。设 (g_{u,j}=sumlimits_{i=1}^{n}dbinom{operatorname{dis}(i,u)}{j}) ，一样的思路转移，只不过烦一点。
转移的时候要非常小心边界，有些没法转移的要直接去掉。
方程大概长这样：
[g_{u,j}=f_{u,j}+g_{fa_u,j-1}-f_{u,j-1}-f_{u,j-2}+g_{fa_u,j}-f_{u,j}-f_{u,j-1}
]
主要思路就是：自己子树内的贡献，加上从父亲 除了自己子树内的部分 过来的贡献。
const int N=50005;
const int K=152;
#define mod 10007
void fmod(int&x){x-=mod,x+=x>>31&mod;}
int n,k,f[N][K],g[N][K],S[K][K];
int hed[N],et;
struct edge{int nx,to;}e[N<<1];
void adde(int u,int v){e[++et].nx=hed[u],e[et].to=v,hed[u]=et;}
void dfs1(int u,int ft){
f[u][0]=1;
for(int i=hed[u];i;i=e[i].nx){
int v=e[i].to;if(v==ft)continue;
dfs1(v,u);
rep(j,0,k){
if(j>0)fmod(f[u][j]+=f[v][j-1]);
fmod(f[u][j]+=f[v][j]);
}
}
}
void dfs2(int u,int ft){
for(int i=hed[u];i;i=e[i].nx){
int v=e[i].to;if(v==ft)continue;
rep(j,0,k){
g[v][j]=f[v][j];
g[v][j]=(g[v][j]+g[u][j]-f[v][j])%mod;
if(j>0){
g[v][j]=(g[v][j]+mod-f[v][j-1])%mod;
g[v][j]=(g[v][j]+g[u][j-1]-f[v][j-1]+mod)%mod;
if(j>1)g[v][j]=(g[v][j]+mod-f[v][j-2])%mod;
}
}
dfs2(v,u);
}
}
signed main(){
n=read(),k=read();
rep(i,2,n){int x=read(),y=read();adde(x,y),adde(y,x);}
S[1][1]=1;
rep(i,2,k)rep(j,1,k)S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%mod;
dfs1(1,0);
rep(i,0,k)g[1][i]=f[1][i];
dfs2(1,0);
for(int i=1;i<=n;++i){
int res=0;
for(int j=0,fac=1;j<=k;++j,fac=1ll*fac*j%mod)fmod(res+=1ll*S[k][j]*fac%mod*g[i][j]%mod);
printf("%d
",res);
}
return 0;
}