记录编号	610259	评测结果	AAAAAAAAAAAAAA
题目名称	重建道路	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.047 s
提交时间	2025-12-18 23:03:00	内存使用	3.77 MiB

#include<iostream>
#include<cstring>
using namespace std;

const int MAXN = 155;

struct node{
	int to, nxt;
}e[MAXN];
int sz[MAXN], n, p;
int h[MAXN], tot = 0;
void add(int x, int y){
	e[++ tot] = {y, h[x]};
	h[x] = tot;
}

int f[MAXN][MAXN];

void dfsz(int u, int fa){
	sz[u] = 1;
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		dfsz(v, u);
		sz[u] += sz[v];
	}
	f[u][0] = 0;
	f[u][sz[u]] = 1;
}

int ans = 1e9;

void dfs(int u, int fa){
	for(int i = h[u];i;i = e[i].nxt){
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v, u);
		for(int j = sz[u] - 1;j >= 0;j --){
			for(int k = 0;k <= j;k ++){
				f[u][j] = min(f[u][j], f[u][j - k] + f[v][k]);
			}
		}
	}
	if(sz[u] - p >= 0){
        if(u == 1) ans = min(ans, f[u][sz[u] - p]);
        else ans = min(ans, f[u][sz[u] - p] + 1);
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> p;

	for(int i = 1;i < n;i ++){
		int u, v; cin >> u >> v;
		add(u, v); add(v, u);
	}
	memset(f, 0x3f3f3f, sizeof(f));
	dfsz(1, 0);
	dfs(1, 0);
	cout << ans << '\n';
	return 0;
}