记录编号	575822	评测结果	AAAAAAAAAAAAAA
题目名称	重建道路	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-09-28 20:15:53	内存使用	0.00 MiB

#include <bits/stdc++.h>
#define pb emplace_back

const int INF = 0x3f3f3f3f;
const int maxn = 205;
std::vector<int> G[maxn];
int n,sz[maxn],f[maxn][maxn],ans,m;

void dfs(int u,int fa) {
	memset(f[u] , 0x3f , sizeof(f[u]));
	f[u][1] = G[u].size();
	sz[u] = 1;
	for(auto& v : G[u]) {
		if(v == fa)continue ;
		dfs(v , u);
		int res[maxn];
		memset(res , 0x3f , sizeof(res));
		for(int j = 1;j <= sz[u];++ j) {
			for(int k = 1;k <= sz[v];++ k) {
				res[j + k] = std::min(res[j + k] , f[u][j] + f[v][k] - 2);
			}
		}
		sz[u] += sz[v];
		for(int i = 1;i <= sz[u];++ i)f[u][i] = std::min(f[u][i] , res[i]);
	}
	if(sz[u] >= m)ans = std::min(ans , f[u][m]);
	return ;
}

int main() {
	freopen("reroads.in","r",stdin);
	freopen("reroads.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(int i = 1;i < n;++ i) {
		int u,v;
		scanf("%d %d",&u,&v);
		G[u].pb(v);
		G[v].pb(u);
	}

	ans = INF;
	dfs(1 , 0);

	printf("%d\n",ans);
	return 0;
}