这个题......我谔谔
首先可以考虑换根(dp)，但到后来发现二项式定理展开过后需要维护(k)个值，同时每个值也要(O(k))的时间按二项式定理算 当然fft优化过后就是k log k了...
这样复杂度是(O(nk^2))的
当然(FFT)优化过后就变成(O(nk log k))了
这复杂度感觉是对的？但FFT的大常数好像被卡成(50)了 跟没优化一样，没试过qwq
然后发现又可以点分治，复杂度(O(nk log n))，跑的好像比(O(nk log k))的FFT换根dp快？然后也收获了(50)分的好成绩...这真是令人谔谔
好像还有FFT优化点分治的，就可以过了，然而窝不会...
这里应该有一个更妙的做法。
注意到(x^n)，其组合意义就是把(n)个不同的求随便往(x)个不同的盒子里扔的方案数。
这样有些盒子是空的，枚举有求的盒子个数，可以得到
其实上面那个(k)的范围到(n)也是可以的，因为大于(x)过后下降幂将会变成(0)，下面为了好看就到(n)吧
其中(egin{Bmatrix}n\kend{Bmatrix})表示第二类斯特林数，([x]_k = prodlimits_{i=0}^{k-1}(x-i))，注意因为(n ge 1)，所以(egin{Bmatrix}n\0end{Bmatrix}=0)，(k)从(0)开始也没事。
更进一步的将下降幂写成组合数的形式有
写到题目里的柿子去
考虑怎么计算后面的(sum)，这个鉴于这棵树没有边权，以及组合数的递推性质，后面的东西可以换根(dp)。
具体的，先以(1)号点为根，令
(v in x)表示(v)在(x)的子树内，(v in son_x)表示(v)是(x)的一个儿子
那么由于
有转移
特别的(dp[x][0]=sumlimits_{v in son_x} dp[v][0])
那再令(f[x][j])表示以(x)为根时的和，换根(dp)算出(f[x][j])就好了，最后的答案
预处理出斯特林数和阶乘就好了，复杂度(O(nk + k^2))
(Code:)
#include <bits/stdc++.h>
using namespace std;
#define fore(i,x) for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
const int N=5e4+10,P=10007;
inline int add(int x,int y){return (x+=y)>=P?x-P:x;}
inline int sub(int x,int y){return (x-=y)<0?x+P:x;}
inline int fpow(int x,int y)
{
int ret=1; for(;y;y>>=1,x=1ll*x*x%P)
if(y&1) ret=1ll*ret*x%P;
return ret;
}
int n,K;
struct edge
{
int to,nxt;
}e[N<<1];
int head[N],cnt=0;
inline void ade(int x,int y)
{e[++cnt]=(edge){y,head[x]};head[x]=cnt;}
inline void addedge(int x,int y){ade(x,y),ade(y,x);}
int dp[N][233],f[N][233];
void dfs(int x,int prev)
{
dp[x][0]=1;
fore(_,x) if(v!=prev)
{
dfs(v,x);
dp[x][0]=add(dp[x][0],dp[v][0]);
for(int i=1;i<=K;i++)
dp[x][i]=add(dp[x][i],add(dp[v][i-1],dp[v][i]));
}
}
void getans(int x,int prev)
{
fore(_,x) if(v!=prev)
{
static int fx[233];
fx[0]=sub(f[x][0],dp[v][0]);
f[v][0]=add(dp[v][0],fx[0]);
for(int i=1;i<=K;i++) fx[i]=sub(f[x][i],add(dp[v][i-1],dp[v][i]));
for(int i=1;i<=K;i++)
f[v][i]=add(dp[v][i],add(fx[i-1],fx[i]));
getans(v,x);
}
}
int S[233][233],fac[233];
int main()
{
scanf("%d%d",&n,&K);
fac[0]=1;for(int i=1;i<=K;i++) fac[i]=fac[i-1]*i%P;
S[0][0]=1;
for(int i=1;i<=K;i++)
for(int j=1;j<=K;j++)
S[i][j]=add(S[i-1][j]*j%P,S[i-1][j-1]);
for(int i=1,x,y;i<n;i++)
scanf("%d%d",&x,&y),addedge(x,y);
dfs(1,0);
for(int i=0;i<=K;i++) f[1][i]=dp[1][i];
getans(1,0);
for(int i=1;i<=n;i++)
{
int ans=0;
for(int j=0;j<=K;j++)
ans=add(ans,S[K][j]*fac[j]%P*f[i][j]%P);
printf("%d
",ans);
}
return 0;
}