Description

【题意】
约翰有 N 个牛棚，这些牛棚间有 N − 1 条双向道路。第 i 条道路连接了第 Ai 个牧场和第 Bi 个牧场，Ai 和 Bi 被称为邻居。任意两牛棚都可以通过道路连通。
约翰得到消息，洪水将要到来了，于是他打算把奶牛集中安置到避难点。避难点必须由相邻的 P个牛棚组成。他还要切断这些牛棚和其他牛棚之间的道路。请问约翰该选择哪些牛棚作为避难点，才能使得需要切断的道路最少呢？

【输入格式】
第一行：两个整数 N 和 P，1 ≤ P ≤ N ≤ 150。
第二行到 N 行：第 i + 1 行有两个整数：Ai 和 Bi，1 ≤ Ai, Bi ≤ N。

【输出格式】
单个整数，表示需要切断的道路数量。

【样例输入】
11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11

【样例输出】
2

【解释】
选择 {1, 2, 3, 6, 7, 8}，需要切断的是 (1, 4) 和(1, 5)

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=200;
int f[N][N], d[N], n, p;
vector<int> G[N];
void dfs(int x, int fa){
	f[x][1]=d[x];
	for(int y: G[x]) if(y!=fa){
		dfs(y, x);
		for(int i=p; i>=1; i--){
			for(int j=1; j<i; j++){
				f[x][i]=min(f[x][i], f[x][j]+f[y][i-j]-2);
			}
		}
	}
}
int main(){
	scanf("%d%d", &n, &p);
	memset(d, 0, sizeof(d));
	for(int i=1; i<n; i++){
		int x, y; scanf("%d%d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
		d[x]++; d[y]++; 
	} 
	memset(f, 0x3f, sizeof(f));
	dfs(1, 0);
	int ans=0x3f3f3f3f;
	for(int i=1; i<=n; i++) ans=min(ans, f[i][p]);
	printf("%d\n", ans);
	return 0;
}