原题链接： 重建道路

题意：给定一个 $n$ 个点的树，求最少删几条边可以剩下一个 $m$ 个点的连通块。
$n \leq 150$

树形DP

由于数据范围很小，所以可以遍历每一个点，
令这个点为根，考虑剪掉哪些子树剩下 $m$ 个点的剪枝次数最少
这个问题等价于删掉 $n - m$ 个点似的剪枝次数最少

一次 $dfs$ 预处理子树大小 $sz[u]$

定义状态 $f[u][k]$ 以 $u$ 为根的子树想要删掉 $k$ 个点至少需要删几条边
显然 $f[u][sz[u]]$ 为 $1$，我们只需要剪掉它与其父节点相连的边，即可剪掉整颗子树

递归搞完子树之后更新状态的过程就是01背包

C++ 代码

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

using namespace std;

const int N = 160, M = N * 2, INF = 0x3f3f3f3f;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int n, m;
int sz[N];
void dfs(int u, int fa)
{
    sz[u] = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa)  continue;
        dfs(j, u);
        sz[u] += sz[j];
    }
}

int res = INF;
int f[N][N];                    //  f[u][k]以u为根的子树想要删掉k个点至少需要删几条边
void dfs2(int u, int fa)
{
    f[u][0] = 0;
    f[u][sz[u]] = 1;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa)  continue;
        dfs2(j, u);
        for(int k = sz[u]; k >= 0; k --)
            for(int l = 0; l <= min(sz[j], k); l ++)
                f[u][k] = min(f[u][k], f[u][k - l] + f[j][l]);
    }
    //for(int i = 0; i <= sz[u]; i ++)  printf("f[%d][%d] = %d\n", u, i, f[u][i]);
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    for(int i = 1; i <= n; i ++)
    {
        dfs(i, -1);
        memset(f, 0x3f, sizeof f);
        dfs2(i, -1);
        res = min(res, f[i][n - m]);
    }
    printf("%d", res);
    return 0;
}