【每日一题】树

statement

将n个点的树分成不超过k个连通块，并分别上色，统计方案数。

solution

设为将点u的子树分成i个连通块的方案数。
考虑如何将子树v的结果合并到u，那么有：

其中第一条式子表示，原子树u分成i个连通块，子树v分成j个连通块，合并后u和v属于同一连通块的方案数。
第二条式子表示，原子树u分成i个连通块，子树v分成j个连通块，合并后u和v不属于同一连通块的方案数。

这就是一个简单的树形dp了，注意在枚举i和j的时候，只要枚举到（或）即可，这样可以使复杂度从降低到。

最终的结果为

code

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int mod = 1e9 + 7;

int add(int x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
  return x;
}
int mul(int x, int y) {
  return 1ll * x * y % mod;
}

vector<int> G[305];
int n, k, size[305], dp[305][305];

void dfs(int u, int f) {
  size[u] = 1, dp[u][1] = 1;
  int tdp[305] = { 0 };
  for (int v : G[u]) {
    if (v == f) {
      continue;
    }
    dfs(v, u);
    fill(tdp, tdp + 1 + min(k, size[u] + size[v]), 0);
    for (int i = 1; i <= min(k, size[u]); i++) {
      for (int j = 1; j <= min(k - i + 1, size[v]); j++) {
        tdp[i + j - 1] = add(tdp[i + j - 1], mul(dp[u][i], dp[v][j]));
        if (i + j <= k) {
          tdp[i + j] = add(tdp[i + j], mul(dp[u][i], dp[v][j]));
        }
      }
    }
    copy(tdp, tdp + 1 + min(size[u] + size[v], k), dp[u]);
    size[u] += size[v];
  }
}

int main() {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  cin >> n >> k;
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    G[x].push_back(y), G[y].push_back(x);
  }
  dfs(1, -1);
  int A = 1, res = 0;
  for (int i = 1; i <= k; i++) {
    A = mul(A, k - i + 1);
    res = add(res, mul(dp[1][i], A));
  }
  cout << res << "\n";
}