题目

https://www.luogu.org/problem/show?pid=1272

代码（想看的先跳）

分析

这道题毕竟是基础算法，很简单。设表示使得以为根的个节点的子树被剥离开来最少需要删除的边数。（我们知道DP有最重要的两个部分：临界值和状态转移方程）

临界值，其中表示所有与相连的边数（包括连接父节点的那条），因为节点数为1就意味着只剩下节点，所以连着的所有边都要切掉。

从题目中的样例来看，可以知道，切掉的是1->2和2->8；，删了下面的4条边。那么是多少呢？肯定和、有关。通过观察、计算和瞎猜，我们可以知道。

如图，要想把1的那1个节点和2的那3个节点连起来，有两刀是多余的。

所以设的一个子节点为，有状态转移方程。

（那可能有的小朋友们就要问了：万一的k个节点中有呢？

不不不，那是不可能的。因为在枚举的子节点的时候，已经通过前面的几个儿子得到了，所以在与的第一次运算中不可能会有与重合的信息。）

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m,a,b,du[155],f[155][155],ans=0x3f3f3f3f;
vector<int>G[155];
void dfs(int x){
    f[x][1]=du[x];
    int u=G[x].size();
    for(int i=0;i<u;i++){
        int v=G[x][i];
        dfs(v);
        for(int j=m;j>1;j--)
            for(int k=1;k<j;k++){
                f[x][j]=min(f[x][j],f[x][k]+f[v][j-k]-2);
            }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++) 
            f[i][j]=200;
    for(int i=1;i<n;i++){
        scanf("%d%d",&a,&b);
        G[a].push_back(b),du[a]++,du[b]++;
    }
    dfs(1);
    for(int i=1;i<=n;i++)ans=min(ans,f[i][m]);
    printf("%d",ans);
    putchar('\n');
    return 0;
}