https://www.cnblogs.com/TinyWong/p/10436473.html

HDU 4507

https://en.wikipedia.org/wiki/Stirling_number

經典樹上 DP + 斯特林數分拆冪運算，斯特林數需要學習一下《具體數學》。

//}/* .................................................................................................................................. */ const int N = int(5e4) + 9, K = int(5e2) + 9; VI adj[N]; int n, k; Int S[N][K], f[N][K], g[N][K]; #define v (*it) void dfs1(int u = 1, int p = 0) { f[u][0] = 1; REP_1(i, k) f[u][i] = 0; ECH(it, adj[u]) if (v != p) { dfs1(v, u); REP(i, k+1) f[u][i] += f[v][i]+i*f[v][i-1]; } } void dfs2(int u = 1, int p = 0){ ECH(it, adj[u]) if (v != p) { g[v][0] = g[u][0]; REP_1(i, k) { Int g1 = g[u][i]-(f[v][i]+i*f[v][i-1]); Int g2 = g[u][i-1]-f[v][i-1]-(i-1)*(i-2 >= 0 ? f[v][i-2] : Int(0)); g[v][i] = f[v][i]+g1+i*g2; } dfs2(v, u); } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif S[0][0] = 1; FOR(i, 1, K) REP_1(j, i) S[i][j] = S[i-1][j-1]+S[i-1][j]*j; Rush { RD(n, k); REP_1(i, n) adj[i].clear(); DO(n-1) { int x, y; RD(x, y); adj[x].PB(y); adj[y].PB(x); } dfs1(); REP(i, k+1) g[1][i] = f[1][i]; dfs2(); REP_1(u, n) { Int z = 0; REP(i, k+1) z += S[k][i] * g[u][i]; cout << z << endl; } } }