[ans_x=sumlimits_{i=1}^{n}dis(x,i)^{k}
]
根据通常幂转下降幂公式展开
[=sumlimits_{i=1}^{n}sumlimits_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix}dbinom{dis(x,i)}{j}j!
]
[=sumlimits_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix}j!sumlimits_{i=1}^{n}dbinom{dis(x,i)}{j}
]
[=sumlimits_{j=0}^{k}egin{Bmatrix}k\jend{Bmatrix}j!sumlimits_{i=1}^{n}(dbinom{dis(x,i)-1}{j}+dbinom{dis(x,i)-1}{j-1})
]
距离相差(1)的点就是自己的子树和父亲，对于根节点有
[f[x][j]=sumlimits_{t|fa[t]=x}f[t][j]+f[t][j-1]
]
然后换根(dp)
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=50000+10,p=10007;
int n,k,ans;
int fac[N],ifac[N],inv[N];
int dp[N][155],s[155][155];
int ret[N];
vector<int> eg[N];
inline int fast(int x,int k)
{
int ret=1;
while(k)
{
if(k&1) ret=ret*x%p;
x=x*x%p;
k>>=1;
}
return ret;
}
inline void init(int n)
{
inv[1]=1;
for(int i=2;i<=n;++i) inv[i]=(-(p/i)*inv[p%i]%p+p)%p;
fac[0]=ifac[0]=1;
for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%p,ifac[i]=ifac[i-1]*inv[i]%p;
}
inline void string2(int n)
{
s[0][0]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
s[i][j]=(s[i-1][j-1]+j*s[i-1][j])%p;
}
inline void dfs1(int now,int fa)
{
dp[now][0]=1;
for(auto t:eg[now])
{
if(t==fa) continue;
dfs1(t,now);
for(int i=1;i<=k;++i) dp[now][i]=(dp[now][i]+dp[t][i]+dp[t][i-1])%p;
dp[now][0]=(dp[now][0]+dp[t][0])%p;
}
}
inline void dfs2(int now,int fa)
{
for(int i=0;i<=k;++i)
ret[now]=(ret[now]+s[k][i]*fac[i]%p*dp[now][i]%p)%p;
for(auto t:eg[now])
{
if(t==fa) continue;
for(int i=1;i<=k;++i) dp[now][i]=(dp[now][i]-dp[t][i]-dp[t][i-1]+2*p)%p;
dp[now][0]=(dp[now][0]-dp[t][0]+p)%p;
for(int i=1;i<=k;++i) dp[t][i]=(dp[t][i]+dp[now][i]+dp[now][i-1])%p;
dp[t][0]=(dp[t][0]+dp[now][0])%p;
dfs2(t,now);
for(int i=1;i<=k;++i) dp[t][i]=(dp[t][i]-dp[now][i]-dp[now][i-1]+2*p)%p;
dp[t][0]=(dp[t][0]-dp[now][0]+p)%p;
for(int i=1;i<=k;++i) dp[now][i]=(dp[now][i]+dp[t][i]+dp[t][i-1])%p;
dp[now][0]=(dp[now][0]+dp[t][0])%p;
}
}
inline void main()
{
n=read(),k=read();
init(n);string2(k);
for(int x,y,i=1;i<n;++i)
{
x=read(),y=read();
eg[x].push_back(y);eg[y].push_back(x);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=n;++i) printf("%lld
",ret[i]);
}
}
signed main()
{
red::main();
return 0;
}