Luogu P4827 Crash 的文明世界

斯特林数简单题。

题意：给定一棵树，边权都为 1，对于每一个点 $x$，求 $\sum_{i = 1} ^ n \text{dist}(x, i) ^ k$。$n\leq 5\times 10 ^ 4$，$k\leq 150$。

$k$ 次方不好使用组合意义，我们可以考虑利用第二类斯特林数弄出一个组合数：

$$\begin{aligned} x ^ k =& \sum_{i = 0} ^ k {k\brace i} \binom xi i! \end{aligned}$$

那么我们可以求出 $\binom xi$，然后最后利用这个式子计算即可。第二类斯特林数直接 $O(k ^ 2)$ 递推即可。

现在考虑如何求出 $\binom xi$。先考虑暴力以每一个点为根 dfs。容易发现这个其实相当于在一条路径上选出 $i$ 条边的方案数。而这个可以通过简单的树形 DP 求出。具体的，考虑 $f(i)$ 表示已经选了 $i$ 条边的方案数，然后新加入一条边枚举其选不选从而做到 $O(k)$ 转移。

后面的优化思路就很显然了，使用换根 DP 即可做到 $O(nk)$ 的时间复杂度，可以通过。

struct Node {
	int a[K];
	Node() : a{} {}
	int& operator [](int x) { return a[x]; }
	Node& operator +=(Node t) {
		for (int i = 0; i <= k; ++ i) adj(a[i] += t[i] - Mod);
		return *this;
	}
	Node& operator -() {
		for (int i = 0; i <= k; ++ i) adj(a[i] = -a[i]);
		return *this;
	}
	Node operator +(Node t) const { return t += *this; }
	Node operator -(Node t) const { return *this + -t; }
	Node nxt() {
		Node res = *this;
		for (int i = 1; i <= k; ++ i) adj(res[i] += a[i - 1] - Mod);
		return res;
	}
} f1[N], f2[N];

void dfs1(int x, int fa = 0)
{
	f1[x][0] = 1;
	for (int v : g[x])
		if (v ^ fa) dfs1(v, x), f1[x] += f1[v].nxt();
}

void dfs2(int x, int fa = 0)
{
	if (fa) f2[x] = (f1[fa] - f1[x].nxt() + f2[fa]).nxt();
	for (int v : g[x])
		if (v ^ fa) dfs2(v, x);
}

int main()
{
	init();
	std::cin >> n >> k;
	for (int i = 1, u, v; i < n; ++ i)
	{
		scanf("%d %d", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	dfs1(1), dfs2(1);
	for (int i = 1; i <= n; ++ i)
	{
		Node sta = f1[i] + f2[i];
		int res = 0;
		for (int i = 0; i <= k; ++ i)
			res = (res + (LL) S[k][i] * sta[i] % Mod * fact[i]) % Mod;
		printf("%d\n", res);
	}
	return 0;
}