P1272 | Ficon's Paper

树形背包问题， $dp_{u, j}$ 代表以 $u$ 为根节点的子树，得到大小为 $j$ 的连通块所割掉最少的边。

连通块大小其实就是物品的价值，割掉的边数其实就是物品的花费。

两种写法的差异：

初始状态为所有儿子都不选

void dfs(int u) {
  siz[u] = 1;
  dp[u][1] = 0;
  for (auto v : adj[u]) {
    dfs(v);
    siz[u] += siz[v];
    for (int j = siz[u]; j >= 1; j--) {
	  // dp[u][j]++;
      for (int k = 1; k < j && k <= siz[v]; k++) {
        dp[u][j] = min(dp[u][j] + 1, dp[u][j - k] + dp[v][k]);
        // dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k]);
      }
    }
  }
}

当 $j = 1, k = 0$ 时，即不选这个节点， $dp_{u, j}$ 是需要加一的，但是默认选根，即 $j, k \ge 1$ ，这会导致无法进入第二层循环，导致 $dp_{u, j}$ 并没有正确被更新，需要把加一的操作提前到循环外。

即，先把答案更新为不选时的状态，然后再拿它和所有选的状态作比较。

当然也可以把第二层循环改成 $k = 0$ 开始，用 $k = 0$ 代表不选这个节点，就是很不符合直觉，因为我们预先规定了至少选自己。

初始状态为所有儿子都选

void dfs(int u) {
  siz[u] = 1;
  dp[u][1] = (int)adj[u].size();
  for (auto v : adj[u]) {
    dfs(v);
    siz[u] += siz[v];
    for (int j = siz[u]; j >= 1; j--) {
      for (int k = 1; k < j && k <= siz[v]; k++) {
        dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k] - 1);
      }
    }
  }
}

这样就很舒服了，不需要额外去加，只需要考虑选的情况了，而选的情况不会出现 $k=0$ ，不需要特殊考虑。

因为我们规定了 $dp_{u, j}$ 的节点 $u$ 必须选，所以统计答案时，要考虑所有情况，即 $\min_{u=1}^n dp_{u, p}$ 。

最后统计答案时，如果该节点不是 1 号点，那么还要额外割掉一条它到父亲的边。

完整代码：

#include <bits/stdc++.h>
#define ve vector
#define fi first
#define se second
using namespace std;
using ll = long long;
using vi = vector<int>;
using vii = vector<vector<int>>;
const int N = 155;
const int inf = 1e9 + 7;
int n, p;
vi adj[N];
int dp[N][N];
int siz[N];

void dfs(int u) {
  siz[u] = 1;
  dp[u][1] = (int)adj[u].size();
  for (auto v : adj[u]) {
    dfs(v);
    siz[u] += siz[v];
    for (int j = siz[u]; j >= 1; j--) {
      for (int k = 1; k < j && k <= siz[v]; k++) {
        dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k] - 1);
      }
    }
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> p;
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].emplace_back(v);
  }
  memset(dp, 0x3f, sizeof(dp));
  dfs(1);
  int ans = dp[1][p];
  for (int i = 2; i <= n; i++) {
    ans = min(ans, dp[i][p] + 1);
  }
  cout << ans << endl;
  return 0;
}