题意

给出一棵树和一个常数 $m$ ，对于每一个 $i~(1\leq i\leq n)$ ，求 $\sum_{j=1}^n\text{dist}(i,j)^m$ 。

题解

关于斯特林数有性质 $x^n=\sum_{i=1}^n\frac{x!}{(x-i)!}\begin{Bmatrix}n\\i\end{Bmatrix}$ ，组合意义相当于枚举非空盒。

则原题有，

$$\sum_{k=1}^m\begin{Bmatrix}m\\k\end{Bmatrix}k!\sum_{j=1}^n\binom{\text{dist}(i,j)}{k} $$

通过树形 DP 求后面的和式。令 $d_{u,i}$ 表示当上面的 $k=i$ 时子树对 $u$ 的贡献， $\text{up}_{u,i}$ 表示除了 $u$ 子树外的节点对 $u$ 的贡献。

代码

const int N = 5e4 + 5, M = 205, mod = 1e4 + 7;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int head[N], tot;
	struct Edge {
		int to, nxt;
	} e[N << 1];
	void add_edge (int u, int v) {
		e[++tot] = (Edge) {v, head[u]}, head[u] = tot;
	}
	int fac[N], s[M][M];
	int up[N][M], d[N][M];
	void dfs1 (int u, int fa) {
		d[u][0] = 1;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (v == fa) continue;
			dfs1 (v, u);
			d[u][0] += d[v][0];
			for (int k = 1; k <= m; k++) 
				d[u][k] = (d[u][k] + d[v][k] + d[v][k - 1]) % mod;
		}
	}
	void dfs2 (int u, int fa) {
		if (fa) {
			up[u][0] = n - d[u][0];
			for (int k = 1; k <= m; k++) {
				up[u][k] = (up[u][k] + up[fa][k] + up[fa][k - 1]) % mod;
				up[u][k] = (up[u][k] + d[fa][k] + d[fa][k - 1]) % mod;
				up[u][k] = (up[u][k] - d[u][k] - d[u][k - 1]) % mod;
				up[u][k] = (up[u][k] - d[u][k - 1]) % mod;
				if (k > 1) up[u][k] = (up[u][k] - d[u][k - 2]) % mod;
				up[u][k] = (up[u][k] + mod) % mod;
			}
		}
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (v == fa) continue;
			dfs2 (v, u);
		}
	}
	int main () {
		n = Read(), m = Read();
		for (int i = 1; i < n; i++) {
			int u = Read(), v = Read();
			add_edge(u, v), add_edge(v, u);
		}
		s[0][0] = fac[0] = 1;
		for (int i = 1; i <= m; i++) {
			fac[i] = fac[i - 1] * i % mod;
			for (int j = 1; j <= i; j++)
				s[i][j] = (s[i - 1][j] * j % mod + s[i - 1][j - 1]) % mod;
		}
		dfs1(1, 0), dfs2(1, 0);
		for (int i = 1; i <= n; i++) {
			int ans = 0;
			for (int k = 1; k <= m; k++) ans = (ans + 1ll * s[m][k] * fac[k] % mod * (up[i][k] + d[i][k]) % mod) %mod;
			printf ("%d\n", ans);
		}
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}