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

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 310;
int n, p, f[MAXN][MAXN], a[MAXN], b[MAXN], rt, ans;
vector<int> cd[MAXN];
int dfs(int x) {
	int w, sum = 1;
	for(int i = 0; i < cd[x].size(); i ++) {
		int u = cd[x][i];
		w = dfs(u);
		sum += w;
		for(int j = sum; j >= 1; j --) {
			for(int k = 1; k < j; k ++) {
				f[x][j] = min(f[x][j], f[x][j - k] + f[u][k] - 1);
			}
		}
	}
	return sum;
}
int main() {
	freopen("reroads.in", "r", stdin);
	freopen("reroads.out", "w", stdout);
	cin >> n >> p;
	ans = 0x3f3f3f3f;
	for(int i = 1; i < n; i ++) {
		int x, y;
		cin >> x >> y;
		a[x] ++;
		b[y] = 1;
		cd[x].push_back(y);
	}
	memset(f, 0x3f, sizeof(f));
	for(int i = 1; i <= n; i ++) {
		if(!b[i]) {
			rt = i;
		}
		f[i][1] = a[i];
	}
	dfs(rt);
	ans = f[rt][p];
	for(int i = 1; i <= n; i ++) {
		if(f[i][p] < ans) {
			ans = f[i][p] + 1;
		}
	}
	cout << ans;
	return 0;
}