【题解】Crash 的文明世界 第二类 stirling 数 树形 dp ——quhengyi11

#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;
}