一棵 $n$ 个点的树，给一个 $k$，对于每个 $i$，求 $sumlimits_{j=1}^n dist(i,j)^k$，膜 10007
$n leq 50000,k leq 150$
sol：
用一个斯特林数公式 $dist(i,j)^k = sumlimits_{l=1}^k inom{dist(i,j)}{l} imes l! imes Stirling2(k,l)$
于是要求的就是 $sumlimits_{l=1}^k Stirling2(k,l) imes l! imes sumlimits_{j=1}^n inom{dist(i,j)}{l}$
第二类斯特林数和阶乘可以预处理，主要是要求 $inom{dist(i,j)}{l}$
可以用组合数递推公式 $inom{i}{j} = inom{i-1}{j} + inom{i-1}{j-1}$
做一个树形 dp，$up_{(i,j)}$ 表示除了 $i$ 子树里的点，二项式系数下面那个数为 $j$ ，对 $i$ 答案的贡献，$dw_{(i,j)}$ 表示 $i$ 子树里的点，二项式系数下面那个数为 $j$ ，对 $i$ 答案的贡献
$dw_{(i,j)}$ 很好转移
$up_{(i,j)}$ 就用它和它的父亲容斥一下，注意根没有父亲
还有注意，这题模数是 $10007$，而 $n$ 是 $50000$，不把 $n$ 模一下就挂了
#include <bits/stdc++.h> #define LL long long #define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i) #define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i) using namespace std; inline int read() { int x = 0,f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar())if(ch == '-') f = -f; for(; isdigit(ch); ch = getchar())x = 10 * x + ch - '0'; return x * f; } const int maxn = 50010, mod = 10007; //inline void mo(int &x) { x %= mod; x += mod; x %= mod; } inline int inc(int x, int y) { x += y; if(x >= mod) x -= mod; return x; } inline int dec(int x, int y) { x -= y; if(x < 0) x += mod; return x; } inline int mul(int x, int y) { return 1LL * x * y % mod; } int n, k; int first[maxn], to[maxn << 1], nx[maxn << 1], cnt; int s[200][200], fac[200], dw[maxn][200], up[maxn][200]; inline void add(int u, int v) { to[++cnt] = v; nx[cnt] = first[u]; first[u] = cnt; } void dfs_down(int x, int pre) { dw[x][0] = 1; for(int i=first[x];i;i=nx[i]) { if(to[i] == pre) continue; dfs_down(to[i], x); dw[x][0] = inc(dw[x][0], dw[to[i]][0]); rep(j, 1, k) { dw[x][j] = inc(dw[x][j], inc(dw[to[i]][j], dw[to[i]][j - 1])); //cout << "dw: " << x << " " << j << " " << dw[x][j] << endl; } } } int nmod; void dfs_up(int x, int pre) { if(x != 1) { up[x][0] = dec(nmod, dw[x][0]); rep(j, 1, k) { up[x][j] = inc(up[x][j], inc(up[pre][j], up[pre][j - 1])); up[x][j] = inc(up[x][j], inc(dw[pre][j], dw[pre][j - 1])); up[x][j] = dec(up[x][j], inc(dw[x][j], dw[x][j - 1])); up[x][j] = dec(up[x][j], dw[x][j - 1]); if(j >= 2) up[x][j] = dec(up[x][j], dw[x][j - 2]); //cout << "up: " << x << " " << j << " " << up[x][j] << endl; } } for(int i=first[x];i;i=nx[i]) if(to[i] != pre) dfs_up(to[i], x); } int L, A, B, Q, now; int main() { //freopen("1.in","r",stdin); freopen("buff.out","w",stdout); /*n = read(), k = read(); L = read(), now = read(), A = read(), B = read(), Q = read(); for (int i=1;i<n;i++){ now=(now*A+B)%Q; int tmp=i<L?i:L; int x=i-now%tmp,y=i+1; add(x,y); }*/ n = read(), k = read(), nmod = n % mod; rep(i, 2, n) { int u = read(), v = read(); add(u, v); add(v, u); } s[0][0] = fac[0] = 1; rep(i, 1, k) rep(j, 1, i) { s[i][j] = inc(s[i - 1][j - 1], mul(s[i - 1][j], j)); //cout << s[i][j] << " "; } rep(i, 1, k) fac[i] = mul(i, fac[i - 1]); dfs_down(1, 0); dfs_up(1, 0); rep(i, 1, n) { int ans = 0; rep(j, 1, k) { ans = inc(ans, mul(mul(s[k][j], fac[j]), inc(up[i][j], dw[i][j]))); //cerr << mul(s[k][j], fac[j]) << " " << inc(up[i][j], dw[i][j]) << endl; } printf("%d ", ans); } }