自动搬运

查看原文

来自洛谷，原作者为

	y2823774827y 喜欢D人的菜鸡

搬运于2025-08-24 22:04:22，当前版本为作者最后更新于2019-04-15 20:07:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

[国家集训队] Crash 的文明世界

前置

斯特林数$\Longrightarrow$斯特林数及反演总结

做法

$ans_x=\sum\limits_{i=1}^ndis(i,x)^k$

$~~~~~~~~=\sum\limits_{i=1}^n\sum\limits_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}C_{dis(i,x)}^jj!$

$~~~~~~~~=\sum\limits_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits_{i=1}^nC_{dis(i,x)}^j$

$~~~~~~~~=\sum\limits_{j=0}^k\begin{Bmatrix}k\\j\end{Bmatrix}j!\sum\limits_{i=1}^n(C_{dis(i,x)-1}^j+C_{dis(i,x)-1}^{j-1})$

$f[x][j]$表示$x$子树内，关于$x$：$C_{dis(i,x)}^j$的答案

显然有$f[x][j]=\sum\limits_{son}f[son][j]+f[son][j-1]$

当这仅仅对于根有效，所以再做一遍换根$dp$

Code

#include<bits/stdc++.h>
typedef int LL;
const LL maxn=5e4+9,mod=10007,maxm=209;
inline LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<3)+(x<<1)+c-'0'; c=getchar();
    }
    return x*f;
}
struct node{
	LL to,nxt;
}dis[maxn<<1];
LL n,num,K;
LL head[maxn],dp1[maxn][maxm],dp2[maxn][maxm],strl[maxm][maxm],tmp[maxm],fac[maxm];
inline void Add(LL u,LL v){
	dis[++num]=(node){v,head[u]}; head[u]=num;
}
void Dfs1(LL u,LL f){
	dp1[u][0]=1;
	for(LL i=head[u];i;i=dis[i].nxt){
		LL v(dis[i].to);
		if(v==f) continue;
		Dfs1(v,u);
		for(LL j=1;j<=K;++j) dp1[u][j]=(dp1[u][j]+dp1[v][j]+dp1[v][j-1])%mod;
		dp1[u][0]=(dp1[u][0]+dp1[v][0])%mod;
	}
}
void Dfs2(LL u,LL f){
	for(LL i=0;i<=K;++i) dp2[u][i]=dp1[u][i];
	if(f){
		for(LL i=1;i<=K;++i) tmp[i]=(dp2[f][i]-dp1[u][i]+mod-dp1[u][i-1]+mod)%mod;
		tmp[0]=(dp2[f][0]-dp1[u][0]+mod)%mod;
		for(LL i=1;i<=K;++i) dp2[u][i]=(dp2[u][i]+tmp[i]+tmp[i-1])%mod;
		dp2[u][0]=(dp2[u][0]+tmp[0])%mod;
	}
	for(LL i=head[u];i;i=dis[i].nxt){
		LL v(dis[i].to);
		if(v==f) continue;
		Dfs2(v,u);
	}
}
int main(){
	n=Read(); K=Read();
	strl[0][0]=strl[1][1]=1;
	for(LL i=2;i<=K;++i)
	    for(LL j=1;j<=i;++j)
	        strl[i][j]=(strl[i-1][j-1]+j*strl[i-1][j])%mod;
	fac[0]=fac[1]=1;
	for(LL i=2;i<=K;++i) fac[i]=fac[i-1]*i%mod;
	for(LL i=1;i<n;++i){
		LL u(Read()),v(Read());
		Add(u,v); Add(v,u);
	}
	Dfs1(1,0); Dfs2(1,0);
	for(LL i=1;i<=n;++i){
		LL ret(0);
		for(LL j=0;j<=K;++j) ret=(ret+1ll*strl[K][j]*fac[j]*dp2[i][j])%mod;
		printf("%d\n",ret);
	}
	return 0;
}