树形DP，定义状态(dp[i][j])为(i)的子树保留(j)个节点，且i不连接父亲所需要删去的最小值。
初始化：(dp[i][1])等于与(i)相连的边数，只需要保留一个节点且要和父亲断开，那只能是(i)这一个节点，其他跟i相连的节点都要断开。
有转移方程(dp[i][j]=min(dp[i][k]+dp[to][j-k]-2))(to)是(i)的子树中的一点
意思是(i)保留(k)节点的子树，(to)保留(j-k)个节点的子树的删去边的和，(i)此时保留的(k)节点是不包括(to)的，因为(i)在枚举子树的时候每个子树节点只会枚举一次，此时的(dp[i][k])其实并没有更新。
在注意一下(-2)的意思，注意初始化的时候i是与所有边都是断开的，因此一开始i是不和to连接的，同时to也不和i连接，这样转移的话，i是要和to连一起的，因此就多删去了两条边，我们再少删去两条边就需要-2
#include <bits/stdc++.h>
#define N 1001
using namespace std;
int n, p, cnt, lin[N], f[N], degree[N], siz[N];
int dp[N][N];
struct edg {
int to, nex;
}e[N *2];
inline void add(int f, int t)
{
e[++cnt].nex = lin[f];
e[cnt].to = t;
lin[f] = cnt;
degree[f]++;
}
void dfs(int now, int fa)
{
for (int i = lin[now]; i; i = e[i].nex)
{
int to = e[i].to;
if (fa == to)
continue;
dfs(to, now);//预处理出子树的dp值即为dp[i][j]为当前i的子树保留j个节点，且子树不跟i相连所得到的最少连接边数。
}
for (int i = lin[now]; i; i = e[i].nex)
{
int to = e[i].to;
if (fa == to)
continue;
for (int j = p; j >= 1; j--)//注意是01背包，所以如果倒着枚举，可能to的贡献会被算多次
{
for (int k = 1; k < j; k++)//k从小到大其实相当于j-k从大到小了
dp[now][j] = min(dp[now][j], dp[now][j - k] + dp[to][k] - 2);
}
}
}
int main()
{
scanf("%d%d", &n, &p);
for (int i = 1; i < n; i++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
}
memset(dp, 13, sizeof(dp));
for (int i = 1; i <= n; i++)
dp[i][1] = degree[i] , dp[i][0] = 0;
dfs(1, -1);
int minn = 2147483647;
for (int i = 1; i <= n; i++)
minn = min(minn, dp[i][p]);
printf("%d", minn);
return 0;
}
/*
11 11
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11
*/