题意：
给定一个 \(n\) 个点的树，对于每个点 \(u\)，求 \(\sum_{v=1}^{n}(d_{u,v})^k\)。
\(n \le 5 \times 10^4,k \le 150\)。
分析：
一道思路很自然的数学题。
利用第二类斯特林数转化式子：
\[\begin{aligned}
\sum_{v=1}^{n}(d_{u,v})^k
&= \sum_{v=1}^{n} \sum_{j=0}^{k}j!\binom{d_{u,v}}{j}\begin{Bmatrix}k\\j\end{Bmatrix}
\\&= \sum_{j=0}^{k}j!\begin{Bmatrix}k\\j\end{Bmatrix}\sum_{v=1}^{n}\binom{d_{u,v}}{j}
\end{aligned}
\]
考虑使用树形 dp 计算 \(\sum_{v=1}^{n}\binom{d_{u,v}}{j}\) 这一部分。
当以 \(u\) 为根时，记
\[f_{x,j}=\sum_{y \in subtree(x)}\binom{d_{x,y}}{j}
\]
如何转移呢？
由于 \(d_{fa,y}-1=d_{fa,x}\)，考虑拆组合数
\[\binom{d_{x,y}}{j}=\binom{d_{x,y}-1}{j-1}+\binom{d_{x,y}-1}{j}
\]
那么转移就很明显了
\[f_{x,j}=\sum_{y \in son_{x}} f_{y,j}+f_{y,j-1}
\]
可是这样只能处理以 \(u\) 为根的答案，考虑换根 dp。
记 \(ans_{u,i}\) 表示以 \(u\) 为根 dp 时 \(f_{u,i}\) 的值。
考虑根从 \(fa\) 移到 \(x\) 的过程，\(ans_{u,i}=f_{u,i}+z_{i}-z_{i-1}\)。\(z_{i}\) 表示以 \(u\) 为根 dp 时 \(f_{fa,i}\) 的值。
\(z_{i}\) 也很容易得到，\(z_{i}=ans_{fa,i}-f_{x,i}-f_{x,i-1}\)。
时间复杂度 \(O(nk)\)。
代码：
#include <bits/stdc++.h>
#define int long long
#define mod 10007
#define N 50004
#define M 160
using namespace std;
int n, k, res;
vector<int>p[N];
int f[N][M], ans[N][M], fac[N], h[N][M], z[N];
void init() {
h[0][0] = 1;
for(int i = 1; i <= k; i++)
for(int j = 1; j <= i; j++) h[i][j] = (h[i - 1][j - 1] + h[i - 1][j] * j % mod) % mod;
fac[0] = 1;
for(int i = 1; i <= M; i++) fac[i] = fac[i - 1] * i % mod;
}
void dfs(int x, int fa) {
f[x][0] = 1;
for(auto y : p[x]) {
if(y == fa) continue;
dfs(y, x);
f[x][0] = (f[x][0] + f[y][0]) % mod;
for(int i = 1; i <= k; i++) f[x][i] = (f[x][i] + f[y][i] + f[y][i - 1]) % mod;
}
}
void Get(int x, int fa) {
for(int i = 0; i <= k; i++) ans[x][i] = f[x][i];
if(fa) {
for(int i = 1; i <= k; i++) z[i] = (ans[fa][i] - f[x][i] - f[x][i - 1] + mod + mod) % mod;
z[0] = (ans[fa][0] - f[x][0] + mod) % mod;
for(int i = 1; i <= k; i++) ans[x][i] = (ans[x][i] + z[i] + z[i - 1]) % mod;
ans[x][0] = (ans[x][0] + z[0]) % mod;
}
for(auto y : p[x]) {
if(y == fa) continue;
Get(y, x);
}
}
signed main() {
cin >> n >> k;
init();
for(int i = 1, u, v; i < n; i++) {
cin >> u >> v;
p[u].push_back(v);
p[v].push_back(u);
}
dfs(1, 0);
Get(1, 0);
for(int u = 1; u <= n; u++) {
res = 0;
for(int i = 0; i <= k; i++) res = (res + h[k][i] * fac[i] % mod * ans[u][i] % mod) % mod;
cout << res << endl;
}
return 0;
}