https://www.luogu.com.cn/problem/P1272

树形dp
分析下题意就知道是个树上背包

设dp[i][j] 表示以i为根的子树，保留j个节点(包括i)需要去掉的最少边数

首先初始化，dp数组全部初始化为INF
然后对于每个节点u，将dp[u][1]初始化为度数 显然以u为根的子树，保留1个节点，需要把连接到u的所有边都去掉

状态转移
dp[u][j] = min(dp[u][j], dp[u][k] + dp[v][j-k] - 2)
这里为什么要减2呢？因为我们这里要通过v来更新u，因此边u<->v必须要保留
但是dp[u][k]和dp[v][j-k]都已经把边u<->v去掉了，因此需要把多去掉的两个u<->v再给加回来

#include <bits/stdc++.h>
using namespace std;
const int N = 160, INF = 0x3f3f3f3f;
int n, p, son[N];
vector<int> adj[N];
int dp[N][N], du[N]; // dp[i][j] 以i为根的子树，保留j个节点（包括i）需要砍掉的最少边数
void dfs(int u, int fa)
{
  son[u] = 1;
  for (int v : adj[u])
  {
    if (v == fa)
      continue;
    dfs(v, u);
    son[u] += son[v];
  }
}
void dfs2(int u, int fa)
{
  for (auto v : adj[u])
  {
    if (v == fa)
      continue;
    dfs2(v, u);
    for (int j = son[u]; j >= 2; j--) // 注意这里滚动数组优化, 必须倒序遍历
    {
      for (int k = 1; k < j; k++)
      {
        if (dp[u][k] + dp[v][j - k] >= 2)
          dp[u][j] = min(dp[u][j], dp[u][k] + dp[v][j - k] - 2);
      }
    }
  }
}
int main() {
  cin >> n >> p;
  for (int i = 1; i < n; i++) {
    int u, v; // u是v的父节点
    cin >> u >> v;
    du[u]++, du[v]++;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  dfs(1, 0);
  memset(dp, 0x3f, sizeof dp);
  for (int u = 1; u <= n; u++) {
    // 以u为根的子树，保留1个节点（包括u）需要砍掉的最少边数
    dp[u][1] = du[u];
  }
  dfs2(1, 0);
  int ans = INF;
  for (int i = 1; i <= n; i++)
    ans = min(ans, dp[i][p]);
  cout << ans << endl;
  return 0;
}