【题解】蓝魔法师

题意：有一棵 个点的树，求出有多少种断边方案，使得每个连通块大小不超过 。。

边连接的是树上的父亲和儿子节点，可以直接通过树边转移。因此考虑以 为根变成有根树，然后进行树上 DP。

记 表示以 为根的子树中，都满足条件，且 所在连通块大小为 的方案数。

转移类似背包，加入一个子树 时枚举断不断边。

• 断边：无论 连通块大小多大，都是合法方案。那么记 ，用 乘到 中去。
• 不断边：枚举 的连通块大小 ，用 贡献到 ，注意 01 背包的转移顺序。

特别注意加入子树时要按照子树大小从小到大加入保证时间复杂度。总时间复杂度 。

代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

const int MaxN = 2000, MaxK = 2000;
const int Mod = 998244353;

int N, K;
int Siz[MaxN + 5], Fa[MaxN + 5];
int F[MaxN + 5][MaxK + 5];
std::vector<int> Gr[MaxN + 5];

inline int add(int x, int y) { return (x += y) >= Mod ? x - Mod : x; }
inline int sub(int x, int y) { return (x -= y) < 0 ? x + Mod : x; }
inline int mul(int x, int y) { return 1LL * x * y % Mod; }
inline int pw(int x, int y) { int z = 1; for (; y; y >>= 1, x = mul(x, x)) if (y & 1) z = mul(z, x); return z; }
inline int inv(int x) { return pw(x, Mod - 2); }
inline int sep(int x, int y) { return mul(x, inv(y)); }
inline void inc(int &x, int y = 1) { (x += y) >= Mod ? x -= Mod : 0; }
inline void dec(int &x, int y = 1) { (x -= y) < 0 ? x += Mod : 0; }

void init() {
  scanf("%d %d", &N, &K);
  for (int i = 1; i < N; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    Gr[u].push_back(v);
    Gr[v].push_back(u);
  }
}

inline bool siz_cmp(int x, int y) { return Siz[x] < Siz[y]; }

void dfs(int u) {
  Siz[u] = 1;
  for (int i = 0; i < (int) Gr[u].size(); ++i) {
    int v = Gr[u][i];
    if (v == Fa[u]) continue;
    Fa[v] = u;
    dfs(v);
    Siz[u] += Siz[v];
  }
  std::sort(Gr[u].begin(), Gr[u].end(), siz_cmp);
  int s = 1;
  F[u][1] = 1;
  for (int i = 0; i < (int) Gr[u].size(); ++i) {
    int v = Gr[u][i];
    if (v == Fa[u]) continue;
    s += Siz[v];
    int sum = 0;
    for (int j = 1; j <= Siz[v] && j <= K; ++j) inc(sum, F[v][j]);
    for (int j = std::min(s, K); j >= 0; --j) {
      F[u][j] = mul(F[u][j], sum);
      for (int k = std::max(1, Siz[v] + j - s); k <= Siz[v] && k <= j; ++k)
        inc(F[u][j], mul(F[u][j - k], F[v][k]));
    }
  }
}

void solve() {
  dfs(1);
  int ans = 0;
  for (int i = 0; i <= K; ++i) inc(ans, F[1][i]);
  printf("%d\n", ans);
}

int main() {
  init();
  solve();
  return 0;
}