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

题意

求出对于树上每个点 $x$ 的 $\sum_{u = 1}^{n} d i s (x, u)^{k}$ 。所有边长为 1。

思路

根据斯特林反演： $m^{n} = \sum_{j = 0}^{n} {\begin{matrix} n \\ j \end{matrix}} C_{m}^{j} j!$ 可以得到： $\sum_{i = 1}^{n} \sum_{j = 0}^{k} {\begin{matrix} k \\ j \end{matrix}} C_{d i s (x, i)}^{j} j! = \sum_{j = 0}^{k} {\begin{matrix} k \\ j \end{matrix}} j! \sum_{i = 1}^{n} C_{d i s (x, i)}^{j} = \sum_{j = 0}^{k} {\begin{matrix} k \\ j \end{matrix}} j! \sum_{i = 1}^{n} (C_{d i s (x, i) - 1}^{j - 1} + C_{d i s (x, i) - 1}^{j})$ 我们只需要 Dp 一边维护后面的组合数部分的值就行了。最后一步是为了推出转移式，设 $f_{x, j}$ 为 $\sum_{i = 1}^{n} C_{d i s (x, i)}^{j}$ ，则有： $f_{x, j} = \sum_{x \to u} f_{u, j} + f_{u, j - 1}$ 再进行一步换根最后代回原式得出答案即可。

实现

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=5e4+10,mod=10007,maxm=210;
	int ecnt,head[maxn],to[maxn<<1],nxt[maxn<<1];
	inline void addedge(int a,int b){
		to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;
		to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;
	}
	int n,k,f[maxn][maxm],g[maxn][maxm],S[maxm][maxm],mul[maxm];
	void dfs1(int x,int fa){
		f[x][0]=1;
		for(int u,i=head[x];i;i=nxt[i]) if((u=to[i])!=fa){
			dfs1(u,x);
			for(int j=1;j<=k;j++) f[x][j]=(f[x][j]+f[u][j]+f[u][j-1])%mod;
			f[x][0]=(f[x][0]+f[u][0])%mod;
		}
	}
	void dfs2(int x,int fa){
		for(int i=0;i<=k;i++) g[x][i]=f[x][i];
		if(fa){
			static int res[maxm];
			for(int i=1;i<=k;i++) res[i]=(g[fa][i]-f[x][i]-f[x][i-1]+mod*2)%mod;
			res[0]=(g[fa][0]-f[x][0]+mod)%mod;
			for(int i=1;i<=k;i++) g[x][i]=(g[x][i]+res[i]+res[i-1])%mod;
			g[x][0]=(g[x][0]+res[0])%mod;
		}
		for(int u,i=head[x];i;i=nxt[i]) if((u=to[i])!=fa) dfs2(u,x);
	}
	inline void work(){
		n=read(),k=read();
		for(int i=1;i<n;i++) addedge(read(),read());
		S[0][0]=S[1][1]=1;
		for(int i=2;i<=k;i++) for(int j=1;j<=i;j++) S[i][j]=(S[i-1][j-1]+S[i-1][j]*j)%mod;
		mul[0]=1;for(int i=1;i<=k;i++) mul[i]=mul[i-1]*i%mod;
		dfs1(1,0),dfs2(1,0);
		for(int i=1;i<=n;i++){
			int ans=0;
			for(int j=0;j<=k;j++) ans=(ans+1ll*S[k][j]*mul[j]*g[i][j])%mod;
			printf("%d\n",ans);
		}
	}
}
signed main(){
	star::work();
	return 0;
}