k<=150 n<=5e4

## 题解

qhy 作为一个喜欢吃柿子的女孩子，不知道很多众所周知的公式，下面这个就是其中一个 (S 表示第二类 Stirling 数)：

$$x^n=\sum_{k=0}^x S_n^k A_x^k$$

$$ans[u]=\sum_{v \in \mathbf{V}} \sum_{j=0}^k S_k^j A_{dis(u,v)}^j$$

$$ans[u]=\sum_{v \in \mathbf{V}} \sum_{j=0}^k S_k^j C_{dis(u,v)}^j\times j!$$

$$ans[u]=\sum_{j=0}^k S_k^j j! \sum_{v \in \mathbf{V}} C_{dis(u,v)}^j$$

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 50505
#define KK 155
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 10007
#define eps 1e-4
int n, K, u, v, head[N], s[KK][KK], fac[KK];
int f[N][KK], g[KK];  //f[u][j] = sigma_{v = 1}^{n} C_{dis(u, v)}^{j}
struct edge{
int nxt, v;
}e[N << 1];
int tot;
inline void addedge (int u, int v)
{
e[++tot] = (edge) {head[u], v};
head[u] = tot;
}
inline void dfs1 (int u, int fa)
{
f[u][0] = 1;
edge (I, u)
{
if (v == fa) continue;
dfs1(v, u);
f[u][0] = f[u][0] + f[v][0]; //讲真 0 的时候其实这就是个子树大小
fo (i, 1, K)
f[u][i] = (f[u][i] + f[v][i] + f[v][i - 1]) % mod;
}
}
inline void dfs2 (int u, int fa)
{
edge (I, u)
{
if (v == fa) continue;
g[0] = f[u][0] - f[v][0];
fo (i, 1, K)
g[i] = (f[u][i] - f[v][i - 1] - f[v][i]) % mod;
f[v][0] = f[v][0] + g[0];
fo (i, 1, K)
f[v][i] = (f[v][i] + g[i - 1] + g[i]) % mod;
dfs2(v, u);
}
}
int main ()
{
scanf("%d %d", &n, &K);
s[0][0] = 1;
fo (i, 1, K)
fo (j, 1, i)
s[i][j] = (s[i - 1][j - 1] + j * s[i - 1][j]) % mod;
fac[1] = 1;
fo (i, 2, K) fac[i] = fac[i - 1] * i % mod;
fo (i, 2, n)
{
scanf("%d %d", &u, &v);
addedge(u, v);
addedge(v, u);
}
dfs1(1, 0);
dfs2(1, 0);
/*    fo (i, 1, n)
{
fo (j, 1, K)
printf("%d ", f[i][j]);
puts("");
}*/
fo (u, 1, n)
{
ll ans = 0;
fo (i, 0, K)
ans = (ans + s[K][i] * fac[i] % mod * f[u][i] % mod) % mod;
printf("%lld\n", (ans % mod + mod) % mod);
}
return 0;
}


### 5 条评论

#### B_Z_B_Y · 2018年11月8日 2:32 下午

哎， ~~~~~（长叹 = =

#### XZYQvQ · 2018年11月5日 11:02 下午

qhy 作为一个喜欢吃柿子的女孩子

#### quhengyi11 · 2018年11月6日 10:35 上午

嘤嘤嘤 qwq(请自行脑补女孩子的声音