一道树形dp题。

设状态为$dp[x][i]$，表示以$x$为根的子树，保留$i$个节点所需删去最少的边数。

对于一个节点我们有以下决策：

• 去掉son子树$dp[x][i]=dp[x][i]+1$
• 保留son子树$dp[x][i]=dp[x][j]+dp[son][i-j](j<i)$

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

const int INF = 0x3F3F3F;
const int MAXN = 151;

int n, p;
int father[MAXN], son[MAXN], bro[MAXN];

int dp[MAXN][MAXN];

void treedp(int x) {
    dp[x][1] = 0;
  // 初始化
    int cur = son[x];

    while ( cur ) {
        treedp(cur);

        for ( int i = p; i; --i ) {
            int temp = dp[x][i] + 1;
      // 决策1

            for ( int j = 1; j < i; ++j ) 
                temp = min(temp, dp[x][j] + dp[cur][i - j] );
      // 决策2

            dp[x][i] = temp;
        }

        cur = bro[cur];
    // 在另外一颗子树进行状态转移
    }
}

int main() {
    ios::sync_with_stdio(false);

    memset(dp, INF, sizeof(dp));
  // 初始化

    cin >> n >> p;

    int u, v;
    for ( int i = 1; i < n; ++i ) {
        cin >> u >> v;

        father[v] = u;
        bro[v] = son[u]; // 存兄弟节点
        son[u] = v;
    }

    int root = 1;
    while ( father[root] )
        root = father[root];
  // 寻找根节点

    treedp(root);

    int ans = dp[root][p];
    for ( int i = 1; i <= n; i++ )
        ans = min(ans, dp[i][p] + 1);
  // 除了根节点，其它节点形成子树答案都需要加一

    cout << ans << endl;

    return 0;
}