Luogu

分析

$$
\begin{align}
S(u) & =\sum_{v = 1}^n \operatorname{dist}(u,v)^k \\
& = \sum_{v = 1}^n \sum_{i = 0}^k \begin{Bmatrix} k \\ i \end{Bmatrix} {\operatorname{dist}(u,v) \\ i} i!\\
& = \sum_{i = 0}^k \begin{Bmatrix} k \\ i \end{Bmatrix} i! \sum_{v = 1}^n {\operatorname{dist}(u,v)\choose i}
\end{align}
$$

预处理斯特林数和阶乘，换根 DP 求出后面的东西即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 50000 + 10, K = 150 + 10;
const int mod = 10007;

int n, k, S[K][K], fac[K];
vector<int> E[N];

int f[N][K], g[N][K], h[K];
void dfs1(int u, int fa) {
    f[u][0] = 1;
    for (int v: E[u]) {
        if (v == fa) continue;
        dfs1(v, u);
        for (int j = 0; j <= k; ++j) {
            f[u][j] = (f[u][j] + f[v][j]) % mod;
            if (j) f[u][j] = (f[u][j] + f[v][j - 1]) % mod;
        }
    }
}
void dfs2(int u, int fa) {
    for (int i = 0; i <= k; ++i) g[u][i] = f[u][i];
    if (fa) {
        for (int i = 0; i <= k; ++i) h[i] = g[fa][i];
        for (int i = 0; i <= k; ++i) {
            h[i] = (h[i] - f[u][i] + mod) % mod;
            if (i) h[i] = (h[i] - f[u][i - 1] + mod) % mod;
        }
        for (int i = 0; i <= k; ++i) {
            g[u][i] = (g[u][i] + h[i]) % mod;
            if (i) g[u][i] = (g[u][i] + h[i - 1]) % mod;
        }
    }
    for (int v: E[u])
        if (v != fa) dfs2(v, u);
}

int main() {
    n = read(), k = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        E[u].emplace_back(v), E[v].emplace_back(u);
    }
    for (int i = S[0][0] = 1; i <= k; ++i)
        for (int j = 1; j <= i; ++j)
            S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j]) % mod;
    fac[0] = 1;
    for (int i = 1; i <= k; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
    dfs1(1, 0), dfs2(1, 0);
    for (int i = 1; i <= n; ++i) {
        int ans = 0;
        for (int j = 1; j <= k; ++j)
            ans = (ans + 1ll * S[k][j] * fac[j] % mod * g[i][j]) % mod;
        printf("%d\n", ans);
    }
    return 0;
}