记录编号	575771	评测结果	AAAAAAAAAAAAAA
题目名称	重建道路	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-09-26 10:36:50	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
struct node{
    int to,next;
}e[160*2];
int du[160],a[160],dp[160][160];
int n,k,res=0x3f3f3f3f,cnt=0;
void add(int u,int v){
    int p=++cnt;
    e[p].to=v;e[p].next=a[u];
    a[u]=p;
}
void dfs(int u,int fa){
    dp[u][1]=du[u];
    for(int p=a[u];p;p=e[p].next){
        int v=e[p].to;
        if(v!=fa){
            dfs(v,u);
            for(int j=k;j>=1;j--){
            	for(int k=1;k<=j;k++){
            		dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]-2);
            	}
            }
        }
    }
    res=min(res,dp[u][k]);
}
int main(){
	freopen("reroads.in","r",stdin);
	freopen("reroads.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
    memset(dp,0x3f3f3f3f,sizeof(dp));
    int u,v;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
        du[u]++;du[v]++;
    }
    dfs(1,0);
    cout<<res<<endl;
    return 0;
}