题意
给定一个有 $n$ 个结点的树，设 $S(i)$ 为第 $i$ 个结点的“指标值”，定义为 $S(i)=\sum_{i=1}^{n}dist(i,j)^k$，$dist(i, j)$ 为结点 $i$ 到结点 $j$ 的最小距离。请输出每个结点的指标值。($n \leq 5000, k \leq 150$)
分析
一个常用的转化
$$n^k=\sum_{i=0}^{k}S(k,i) \times C(n,i) \times i!$$
证明可以考虑组合意义，等式的左边就是把 $k$ 个球放在 $n$ 个盒子里；右边就是枚举非空盒子的数量 $i$，注意到这里的盒子是不同的，所以还要乘上一个 $i!$。
利用上面写的那个常用的转化。令 $dp[i][j]=\sum\limits_{k=1}^{n}C(dist(i,k),j)$，那么答案为 $ans_i$就可以表示成 $ans_i=\sum\limits_{j=1}^{k}S(k,j) \times j! \times dp[i][j]$。注意到 $dp[i][j]$ 是组合数是可以直接转移的，具体如下：
From: 链接
#include<cstdio>
#include<iostream>
using namespace std;
int n,k,head[];
const int mod=;
struct edg{
int to,next;
}e[];
int S[][],mi[];
int size,fd[][],fu[][];
void add(int x,int y){size++;e[size]={y,head[x]};head[x]=size;}
void dfs1(int x,int fa)
{
fd[x][]=;
for (int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if (y==fa) continue;
dfs1(y,x);
for (int j=;j<=k;j++)
{
if (j)
fd[x][j]=(fd[x][j]+fd[y][j]+fd[y][j-])%mod;
else fd[x][j]=(fd[x][j]+fd[y][j])%mod;
}
}
}
void dfs2(int x,int fa)
{
if (fa)
{
for (int i=;i<=k;i++)
{
if (i)
{
fu[x][i]=(fu[x][i]+fu[fa][i]+fu[fa][i-])%mod;
fu[x][i]=(fu[x][i]+fd[fa][i]+fd[fa][i-])%mod;
fu[x][i]=(fu[x][i]-(fd[x][i]+fd[x][i-])%mod+mod)%mod;
fu[x][i]=(fu[x][i]-fd[x][i-]+mod)%mod;
if (i>) fu[x][i]=(fu[x][i]-fd[x][i-]+mod)%mod;
}
else fu[x][]=n-fd[x][];
}
}
for (int i=head[x];i;i=e[i].next)
{
int y=e[i].to;
if (y==fa) continue;
dfs2(y,x);
}
}
int main()
{
scanf("%d%d",&n,&k);
mi[]=;for (int i=;i<=k;i++) mi[i]=mi[i-]*i%mod;
S[][]=;
for (int i=;i<=k;i++)
for (int j=;j<=i;j++)
S[i][j]=(S[i-][j-]+j*S[i-][j])%mod;
for (int x,y,i=;i<n;i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs1(,);dfs2(,);
for (int i=;i<=n;i++)
{
int ans=;
for (int j=;j<=k;j++)
ans=(ans+1ll*S[k][j]*mi[j]*(fd[i][j]+fu[i][j]))%mod;
printf("%d\n",ans);
}
}
参考链接：
1. https://blog.****.net/Charlie_jilei/article/details/79922722