Description：

给一棵树，对于每个点，求： $$ S(i)=\sum_{j=1}^{n}{\rm dist}(i,j)^k $$ $1\leqslant n\leqslant50000$

Solution：

显然是二次扫描与换根法，但是那个 $k$ 次方不太好做，考虑利用第二类斯特林数把他拆开，即： $$ \begin{align} S(t)&=\sum_{j=1}^n\sum_{i=0}^kS_2(k,i)C({\rm dist}(t,j),i)i!\\ &=\sum_{i=0}^kS_2(k,i)\times i!\times\sum_{j=1}^nC({\rm dist}(t,j),i) \end{align} $$ 设： $$ f[k][i]=\sum_{j\ in\ subtree\ of\ i}^nC({\rm dist}(k,j),i) $$

$$ \begin{align} \sum_{j\ in\ subtree\ of\ k}^nC({\rm dist}(k,j),i)&=\sum_{fa[x]=k}\sum_{j\ in\ subtree\ of\ x}C({\rm dist}(x,j)+1,i)\\ f[k][i]&=\sum_{fa[x]=k}\sum_{j\ in\ subtree\ of\ x}\biggl(C({\rm dist}(x,j),i)+C({\rm dist}(x,j),i-1)\biggr)\\ f[k][i]&=\sum_{fa[x]=k}f[x][i]+f[x][i-1] \end{align} $$

然后第二遍 $DP$ 的时候再倒着推就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 50010

#define MAXK 160

#define MOD 10007

int S[MAXK][MAXK];

int fac[MAXK];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int f[MAXN][MAXK];

bool vis[MAXN];

void dp1(int k)

{

	vis[k] = true;

	f[k][0] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		dp1(e[i].to);

		for(int x = 0;x <= m;++x)

		{

			f[k][x] = (f[k][x] + f[e[i].to][x]) % MOD;

			if(x != 0)f[k][x] = (f[k][x] + f[e[i].to][x - 1]) % MOD;

		}

	}

	vis[k] = false;

	return;

}

int g[MAXK]; 

void dp2(int k)

{

	vis[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(vis[e[i].to])continue;

		for(int x = 0;x <= m;++x)g[x] = f[k][x];

		for(int x = 0;x <= m;++x)

		{

			f[k][x] = (f[k][x] - f[e[i].to][x] + MOD) % MOD;

			if(x != 0)f[k][x] = (f[k][x] - f[e[i].to][x - 1] + MOD) % MOD;

		}

		for(int x = 0;x <= m;++x)

		{

			f[e[i].to][x] = (f[e[i].to][x] + f[k][x]) % MOD;

			if(x != 0)f[e[i].to][x] = (f[e[i].to][x] + f[k][x - 1]) % MOD;

		}

		for(int x = 0;x <= m;++x)f[k][x] = g[x];

		dp2(e[i].to);

	}

	vis[k] = false;

	return;

}

void init()

{

	S[0][0] = 1;

	fac[0] = 1;

	for(int i = 1;i <= m;++i)

	{

		fac[i] = fac[i - 1] * i % MOD;

		S[i][1] = S[i][i] = 1;

		for(int j = 2;j < i;++j)

		{

			S[i][j] = (S[i - 1][j - 1] + S[i - 1][j] * j) % MOD;

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	init();

	dp1(1);

	dp2(1);

	for(int i = 1;i <= n;++i)

	{

		int ans = 0;

		for(int k = 0;k <= m;++k)

		{

			ans = (ans + S[m][k] * fac[k] % MOD * f[i][k] % MOD) % MOD;

		}

		printf("%d\n",ans);

	}

	return 0;

}