国家集训队 Crash 的文明世界（第二类斯特林数+换根dp）

题意

​ 题目链接：https://www.luogu.org/problem/P4827

​ 给定一棵 (n) 个节点的树和一个常数 (k) ，对于树上的每一个节点 (i) ，求出 (displaystyle sum_{i=1}^n{ m dist}^k(i,j))，其中 ( m{dist}) 函数表示树上两点距离。

​ (1 leq n leq 50000)

​ (1leq k leq 150)

思路

​ 看到求答案 (k) 次方的问题，应该联想到第二类斯特林数，因为第二类斯特林数有如下的式子：

[n^m=sum_{i=0}^{+infty}{nchoose i}left{{matop i} ight}i! ]

​ 可以理解成，(n^m) 表示把 (m) 个不同的球放在 (n) 个不同的盒子中；后面的组合数表示从 (n) 个盒子中选出 (i) 个，斯特林数表示把 (m) 个球分成 (i) 个无序集合，阶乘表示排列。另外，循环上界写乘 (n)，(m) 或者无穷大都是一样的。

​ 假设我们已经维护住了 (n^m) ，我们现在想知道 ((n+1)^m) ，怎么办呢？套入上面的式子，我们得到：

[egin{align*} (n+1)^m&=sum_{i=0}^m{n+1choose i}left{{matop i} ight}i!\ &=sum_{i=0}^m{huge(}{nchoose i}+{nchoose i-1}{huge)}left{{matop i} ight}i! end{align*} ]

​ 我们发现，与 (n^m) 的展开式相比，(displaystyle left{{matop i} ight}i!) 没有变，每个组合数都加上前一项。这似乎在启示我们把组合数独立出来。定义数组 ({a_n}) ，用 (a_i) 表示 (displaystyleleft{{matop i} ight}i!) 的系数，于是，我们得到了一个“数据结构”，能维护一个 (n^m) 形式的数，支持给 (n) 加一。不难发现，加上前一项的操作可以把过程逆转，于是这个“数据结构”也能支持给 (n) 减一，我们姑且称之为“斯特林机”（名字瞎取的，勿喷）。

​ 只能维护一个数也太鸡肋了吧？但我们不难发现，只要 (m) 相同，多个 (n^m) 形式的数可以一起维护，直接把每个斯特林机的 (a_i) 加在一起即可，我们可以称之为合并两个斯特林机；类似的，我们也可以从一个斯特林机中减去另一个斯特林机。这个 ({a_i}) 数组就像插值一样，用一些方便计算的量整体运算，从而得到最后结果。

​ 依靠斯特林机，这道题似乎就变得异常的简单。我们先考虑如何求出 (1) 号节点的答案。

​ 定义 (dp_u) 为 (displaystylesum_{vin{ m subtree(u)}}{ m dist}^k(u,v)) 。由于都是 (k) 次方，那可以把 (dp_u) 开成一个斯特林机的形式。初值每个节点的斯特林机中只有自己，为 (0^0)，每次转移就对儿子的斯特林机执行各元素加一的操作，再加到自己身上。于是，我们得到了以 (1) 为根点答案。然后我们发现，转移中每种操作都能找到其对应的逆操作，于是我们可以很快的写出一个换根 (dp) 。

代码

​ 重载了很多运算符，看着挺优美的。

#include<bits/stdc++.h>
#define FOR(i, x, y) for(int i = (x), i##END = (y);i <= i##END; ++i)
#define DOR(i, x, y) for(int i = (x), i##END = (y);i >= i##END; --i)
template<typename T, typename _T>inline bool chk_min(T &x, const _T y){return y < x? x = y, 1 : 0;}
template<typename T, typename _T>inline bool chk_max(T &x, const _T y){return x < y? x = y, 1 : 0;}
typedef long long ll;
const int N = 50005;
const int P = 10007;
const int M = 153;

int C[M][M], S[M][M], fac[M];
inline void plseq(int &x, int y) {(x += y) >= P ? x -= P : 0;}
inline void mnseq(int &x, int y) {(x -= y) < 0 ? x += P : 0;}

template<const int N, const int M, typename T> struct Linked_List
{
    int head[N], nxt[M], tot; T to[M];
    Linked_List() {clear();}
    T &operator [](const int x) {return to[x];}
    void clear() {memset(head, -1, sizeof(head)), tot = 0;}
    void add(int u, T v) {to[tot] = v, nxt[tot] = head[u], head[u] = tot++;}
    #define EOR(i, G, u) for(int i = G.head[u]; ~i; i = G.nxt[i])
};

int sm;
struct Stirling_Machine
{
	int a[M];
	Stirling_Machine() {}
	Stirling_Machine(int v) {FOR(i, 0, sm) a[i] = C[v][i];}
	void operator +=(const Stirling_Machine &_) {FOR(i, 0, sm) plseq(a[i], _.a[i]);}
	void operator -=(const Stirling_Machine &_) {FOR(i, 0, sm) mnseq(a[i], _.a[i]);}
	void operator ++() {DOR(i, sm, 1) plseq(a[i], a[i - 1]);}
	void operator --() {FOR(i, 1, sm) mnseq(a[i], a[i - 1]);}
	int query()
	{
		int ans = 0;
		FOR(i, 0, sm) plseq(ans, 1ll * a[i] * S[sm][i] % P * fac[i] % P);
		return ans;
	}
};

Linked_List<N, N << 1, int> G;
Stirling_Machine dp[N];
int ans[N];
int n;

void dfs(int u, int f)
{
	dp[u] = Stirling_Machine(0);
	EOR(i, G, u)
	{
		int v = G[i];
		if(v == f) continue;
		dfs(v, u);
		++dp[v];
		dp[u] += dp[v];
	}
}

void redfs(int u, int f)
{
	ans[u] = dp[u].query();
	EOR(i, G, u)
	{
		int v = G[i];
		if(v == f) continue;

		dp[u] -= dp[v];
		--dp[v];
		++dp[u];
		dp[v] += dp[u];

		redfs(v, u);

		dp[v] -= dp[u];
		--dp[u];
		++dp[v];
		dp[u] += dp[v];
	}
}

int main()
{
	fac[0] = fac[1] = 1;
	FOR(i, 2, M - 1) fac[i] = 1ll * fac[i - 1] * i % P;
	FOR(i, 0, M - 1) FOR(j, 0, i)
		C[i][j] = (j == 0 || j == i ? 1 : (C[i - 1][j - 1] + C[i - 1][j]) % P);
	S[0][0] = 1;
	FOR(i, 1, M - 1) FOR(j, 1, i)
		S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j]) % P;

	scanf("%d%d", &n, &sm);
	FOR(i, 1, n - 1)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		G.add(u, v), G.add(v, u);
	}
	dfs(1, 0);
	redfs(1, 0);
	FOR(i, 1, n) printf("%d
", ans[i]);
	return 0;
}