洛谷P1272 重建道路 树形dp

//洛谷P1272 重建道路
//树形dp 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 155;
struct N{
	int nxt,v;
}ed[maxn<<2];
int dp[maxn][maxn],du[maxn];
int head[maxn],cnt,n,p,ans=0x7ffffff;
void add(int u,int v){
	cnt++;
	ed[cnt].v = v;
	ed[cnt].nxt = head[u];
	head[u] = cnt; 
}
void dfs(int u,int fa){
	dp[u][1] = du[u] - (fa!=0);//u为根节点选择i个点要去掉的最小边数 
	for(int v,i=head[u];i;i=ed[i].nxt){
		v = ed[i].v;
		if(v==fa)continue;
		dfs(v,u);
		for(int j=p;j>=1;j--){
			for(int k=1;k<j;k++){
				dp[u][j] = min(dp[u][j],dp[u][k]+dp[v][j-k]-1);
				//一开始把所有边都删了，连接v u 还需要加上一条边
				//所以去掉的边就少一条 	
			}
		}
		
	}
	ans = min(ans,dp[u][p]+(fa!=0)); //不是根结点 还要去掉父结点和自己的连线 
}
int main()
{		
	
	scanf("%d %d",&n,&p);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		du[u]++; du[v]++;
		add(u,v);	add(v,u);
	}
	memset(dp,0x3f,sizeof(dp));
	dfs(1,0);
	printf("%d",ans);
	return 0;
}