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

题目描述

给你一棵 n 个点的树，对于树上的每个节点 i，求 (sum_{j=1}^ndis(i,j)^k)。其中 (dis(i,j)) 为两点在树上的距离。

输入格式

第一行两个整数 n,k。

接下来 n-1 行，每行两个整数 (x,y)，表示一条树边。

输出格式

一行一个整数，表示答案对 10007 取模的值。

样例输入

样例输出

数据范围

对于 (30\%) 的数据，(nle5000,kle50)

对于另 (20\%) 的数据，保证树是一条链

对于所有数据，(nle50000,kle150)

解析

题目要求的值即为(sum_{i=1}^{n}dis(x,i)^k)。形式上可以用第二类斯特林数的性质进行化简。

[egin{align} Ans &= sum_{i=1}^{n}dis(x,i)^k \ &= sum_{i=1}^{n} sum_{j=0}^{k} S(k,j)*j!*C_{dis(x,i)}^{j}\ &= sum_{j=0}^{k}S(k,j)*j!*sum_{i=1}^{n}(C_{dis(x,i)-1}^{j}+C_{dis(x,i)-1}^{j-1})\ end{align} ]

其中斯特林数和阶乘都是可以预处理的。接下来的问题是如何求(sum_{i=1}^{n}C_{dis(x,i)}^{j})。

设(f[i][j])表示对于第i个点的子树中上式的值，则(C_{dis(x,i)-1}^{j})的值可以看做是在i点儿子的f中并由儿子推出(f[i][j])的值。那么我们可以先假设1号点为根节点，用一遍dfs求出f的值，状态转移方程为

[f[i][j]=sum_{son}f[son][j]+f[son][j-1] ]

然后用换根DP求出以任意i点作为根节点时的(f[i][j])即可。最后的答案为

[sum_{j=0}^{k}S(k,j)*j!*f[i][j] ]

动态规划时注意边界条件。

代码

#include <iostream>
#include <cstdio>
#define N 50002
#define K 201
#define int long long
using namespace std;
const int mod=10007;
int head[N],ver[N*2],nxt[N*2],l;
int n,k,i,j,f1[N][K],f2[N][K],g[K],f[K],s[K][K];
void insert(int x,int y)
{
	l++;
	ver[l]=y;
	nxt[l]=head[x];
	head[x]=l;
}
void dfs1(int x,int pre)
{
	f1[x][0]=1;
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(y!=pre){
			dfs1(y,x);
			for(int j=1;j<=k;j++) f1[x][j]=(f1[x][j]+f1[y][j]+f1[y][j-1])%mod;
			f1[x][0]=(f1[x][0]+f1[y][0])%mod;
		}
	}
}
void dfs2(int x,int pre)
{
	for(int i=0;i<=k;i++) f2[x][i]=f1[x][i];
	if(pre){
		for(int i=1;i<=k;i++) g[i]=(f2[pre][i]-f1[x][i]+mod-f1[x][i-1]+mod)%mod;
		g[0]=(f2[pre][0]-f1[x][0]+mod)%mod;
		for(int i=1;i<=k;i++) f2[x][i]=(f2[x][i]+g[i]+g[i-1])%mod;
		f2[x][0]=(f2[x][0]+g[0])%mod;
	}
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(y!=pre) dfs2(y,x);
	}
}
signed main()
{
	freopen("C.in","r",stdin);
	freopen("C.out","w",stdout);
	cin>>n>>k;
	for(i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		insert(u,v);
		insert(v,u);
	}
	s[0][0]=s[1][1]=1;
	f[0]=1;
	for(i=1;i<=k;i++){
		for(j=1;j<=k;j++) s[i][j]=(s[i-1][j-1]+j*s[i-1][j])%mod; 
	}
	for(i=1;i<=k;i++) f[i]=f[i-1]*i%mod;
	dfs1(1,0);
	dfs2(1,0);
	for(i=1;i<=n;i++){
		int ans=0;
		for(j=0;j<=k;j++) ans=(ans+(s[k][j]*f[j]%mod*f2[i][j])%mod)%mod;
		cout<<ans<<endl;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}