hdu4625 JZPTREE

题意:给出一棵树，边权均视为1，对于树上每一个点u，求∑_v dis(u,v)^k

我特意去买了本混凝土数学。。。

《具体数学》:xⁿ=∑_k S₂(n,k)*A(x,k) (S₂表示第二类斯特林数，我不会用Latex别D我。。。)

这个公式的正确性显然，把有x个元素的集合划分为k个集合，允许空集的方案数为xⁿ

再做个简单的变换可以得到:xⁿ=∑_k S₂(n,k)*k!*C(x,k)

则(x+1)ⁿ=∑_k S₂(n,k)*k!*C(x+1,k)

组合数有性质:C(n,k)=C(n-1,k)+C(n-1,k-1)

则(x+1)ⁿ=∑_k S₂(n,k)*k!*(C(x,k)+C(x,k-1))=xⁿ+∑_k S₂(n,k)*k!*C(n,k-1)

实际上，我们容易发现 S₂(n,k)*k! 这个算子一直没有发生改变，所以我们可以预处理出S₂(n,k)*k!的值

令dp[x][k]=∑_{y(y属于以x为根的子树)} C(dis(x,y),k)

则dp[x][k]=∑_{y(y是与x的儿子)} dp[y][k]+dp[y][k-1]

先dfs 一次求出以1为根的所有dp值，再dfs一次，使根为当前节点x并计算 ∑_k S₂(n,k)*k!*dp[x][k]

复杂度:预处理 O(k²)+dp O(nk)

Portal

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;int f=1;
	while(c=g(),c<48||c>57)if(c=='-')f=-1;
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
	x*=f;
}

#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=50005;
const int MAXK=505;
const int Mod=10007;

struct edge{
	int t,n;
	edge(int t=0,int n=0):
		t(t),n(n){}
}e[MAXN<<1];
int head[MAXN],tot;
inline void AddEdge(int s,int t){
	e[++tot]=edge(t,head[s]),head[s]=tot;
	e[++tot]=edge(s,head[t]),head[t]=tot;
}

int n,k;

inline void Init(){
	Scan(n),Scan(k);
	rep(i,1,n+1)head[i]=0;
	tot=0;
	rep(i,1,n){
		int u,v;
		Scan(u),Scan(v);
		AddEdge(u,v); 
	}
}

int T;

int s[MAXK][MAXK],fac[MAXK];

inline void init(){
	s[0][0]=fac[0]=1;
	rep(i,1,MAXK){
		fac[i]=fac[i-1]*i%Mod;
		rep(j,1,MAXK){
			s[i][j]=(j*s[i-1][j]+s[i-1][j-1])%Mod;
		}
	}
	rep(i,1,MAXK)
		rep(j,1,MAXK){
			s[i][j]=s[i][j]*fac[j]%Mod;
		}
}

int dp[MAXN][MAXK];

void prev_dfs(int x,int p){
	dp[x][0]=1;
	rep(i,1,k+1)dp[x][i]=0;
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p){
			prev_dfs(y,x);
			rep(j,0,k+1){
				dp[x][j]+=dp[y][j];
				if(j)dp[x][j]+=dp[y][j-1];
				dp[x][j]%=Mod;
			}
		}
}

int ans[MAXN];

void dfs(int x,int p){
	ans[x]=0;
	rep(i,0,k+1)
		ans[x]=(ans[x]+s[k][i]*dp[x][i])%Mod;
	for(int i=head[x],y;i;i=e[i].n)
		if((y=e[i].t)!=p){
			rep(j,0,k+1){
				dp[x][j]+=Mod-dp[y][j];
				if(j)dp[x][j]+=Mod-dp[y][j-1];
				dp[x][j]%=Mod;
			}
			rep(j,0,k+1){
				dp[y][j]+=dp[x][j];
				if(j)dp[y][j]+=dp[x][j-1];
				dp[y][j]%=Mod;
			}
			dfs(y,x);
			rep(j,0,k+1){
				dp[y][j]+=Mod-dp[x][j];
				if(j)dp[y][j]+=Mod-dp[x][j-1];
				dp[y][j]%=Mod;
			}
			rep(j,0,k+1){
				dp[x][j]+=dp[y][j];
				if(j)dp[x][j]+=dp[y][j-1];
				dp[x][j]%=Mod;
			}
		}
}

inline void Solve(){
	prev_dfs(1,0);
	dfs(1,0);
	rep(i,1,n+1)
		printf("%d\n",ans[i]);
}

int main(){
	for(init(),Scan(T);T--;Init(),Solve());
	return 0;
}