还是先打暴力，枚举 \(k^n\) 种树的形态做树形 DP，时间复杂度 \(\mathcal O(nk^n)\)，拿下 \(n \le 8\) 和 \(k = 1\) 的 \(25\) 分。
虽然很简单，还是交代下吧：设 \(f(u, 0/1)\) 表示以 \(u\) 为根的子树中是否选 \(u\) 的最大权独立集，\(f(u, 0) \gets w_u + \sum\limits_{v \in son_u} \max\{f(v, 0), f(v, 1)\}, f(u, 1) \gets \sum\limits_{v \in son_u} f(v, 0)\)。答案是 \(\max\{f(u, 0), f(u,1)\}\)。
把相同的 \(\mathcal O(n)\) DP 做 \(k^n\) 次很笨蛋，考虑优化这个过程，上 DP 套 DP！
设 \(F(u, i,j)\) 表示 \(f(u, 0) = i, f(u, 1) = j\) 的方案数，转移时考虑逐个加入子结点 \(v\)，有：
\[F(u, i, j) \gets F(u, i, j) + \sum_{p, q \le i} F(u, i - \max\{p, q\}, j - p) \times F(v, p, q) \]一个重要性质是 \(\max\{f(u, 0), f(u, 1) \} \in [f(u, 0), f(u, 0) + k]\)，证明是显然的：\(f(u, 0) \ge f(u, 1) - w_u, w_u \in [1, k]\)。
然后状态数 \(\mathcal O(n^2k^3)\)，时间复杂度 \(\mathcal O(n^4k^4)\)，非常跑不满，但也不可能过，能有 \(60\) 分吧？
不合法状态很多，且转移时用到的是 \(\max\{i, j \}\)，单独记个 \(j\) 显得有些浪费，考虑优化。
根据重要性质，设 \(F(u, i, j)\) 表示 \(f(u, 0) = i, \max\{f(u, 0), f(u, 1)\} = f(u, 0) + j\) 的方案数。
转移时同样是考虑逐个加入子结点 \(v\)，式子挺好推就懒得写了。
初值： \(\forall u, f(u, 0, j) = 1(j \in [1, k])\)。
答案： \(ans_l = \sum\limits_{i + j = l} F(1, i, j)\)。
跑自身 \(\mathcal O(n)\) 树形 DP 的时候，每层的时间复杂度是 \(\mathcal O(n^2k^4)\)，根据主定理，取大的单层时间复杂度，总时间复杂度 \(\mathcal O(n^2k^4)\)。
实际实现时还可以在转移对为 \(0\) 的状态剪枝，飞快！
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int N = 1e3 + 10, K = 5 + 1, MOD = 1e9 + 7;
int n, k, sz[N], f[N][N * K][K], fu[N * K][K];
vector<int> G[N];
inline void add(int u, int v) {G[u].emplace_back(v), G[v].emplace_back(u);}
void dfs(int u, int fa) {
sz[u] = 1;
for (int j = 1; j <= k; j++) f[u][0][j] = 1;
for (int v : G[u]) if (v != fa) {
int maxi = k * sz[u];
dfs(v, u); sz[u] += sz[v];
int maxp = k * sz[v];
for (int i = 0; i <= maxi; i++) {
for (int j = 0; j <= k; j++) if (f[u][i][j]) {
for (int p = 0; p <= maxp; p++) {
for (int q = 0; q <= k; q++) if (f[v][p][q]) {
int x = i + p + q, y = max(j - q, 0);
fu[x][y] = (fu[x][y] + 1ll * f[u][i][j] * f[v][p][q]) % MOD;
}
}
}
}
maxi = k * sz[u];
for (int i = 0; i <= maxi; i++) for (int j = 0; j <= k; j++) f[u][i][j] = fu[i][j], fu[i][j] = 0;
}
}
int main() {
// freopen("2.in", "r", stdin), freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> k;
for (int i = 1, u, v; i < n; i++) cin >> u >> v, add(u, v);
dfs(1, 0); n *= k;
for (int i = 1; i <= n; i++) {
ll ans = 0;
for (int j = max(i - k, 0); j <= i; j++) ans += f[1][j][i - j];
cout << ans % MOD << '\n';
}
return 0;
}