题目描述
给你一棵 n 个点的树，对于树上的每个节点 i，求 \(\sum_{j=1}^ndis(i,j)^k\)。其中 \(dis(i,j)\) 为两点在树上的距离。
输入格式
第一行两个整数 n,k。
接下来 n-1 行，每行两个整数 (x,y)，表示一条树边。
输出格式
一行一个整数，表示答案对 10007 取模的值。
样例输入
5 2
1 2
1 3
2 4
2 5
样例输出
10
7
23
18
18
数据范围
对于 \(30\%\) 的数据，\(n\le5000,k\le50\)
对于另 \(20\%\) 的数据，保证树是一条链
对于所有数据，\(n\le50000,k\le150\)
解析
题目要求的值即为\(\sum_{i=1}^{n}dis(x,i)^k\)。形式上可以用第二类斯特林数的性质进行化简。
\[\begin{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;
}