记录编号	167846	评测结果	AAAAAAAAAAAAAA
题目名称	重建道路	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2015-06-29 15:06:11	内存使用	0.40 MiB

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<fstream>

using namespace std;
typedef vector<int> vi;

const int MAXN = 151;
int n, p, dp[MAXN][MAXN] = {0}, fa[MAXN] = {0}, root, ans = INT_MAX;
vi son[MAXN];
void dfs(int);
ifstream fi("reroads.in");
ofstream fo("reroads.out");
#define cin fi
#define cout fo

main()
{
	ios::sync_with_stdio(0);
	cin >> n >> p;
	for(int i = 1; i < n; i ++)
	{
		int a, b;
		cin >> a >> b;

		fill(dp[i], dp[i] + p + 1, 65536 * 2);
		fa[b] = a;
		son[a].push_back(b);
	}
	fill(dp[n], dp[n] + p + 1, 65536 * 2);
	for(int i = 1; i <= n; i ++)
		if(fa[i] == 0)
		{
			root = i;
			break;
		}
	dfs(root);
	ans = dp[root][p];
	for(int i = 1; i <= n; i ++)
	{
		ans = min(ans, dp[i][p] + 1);
//		cout << dp[i][p] << endl;
	}
	cout << ans;
}

void dfs(int node)
{
	dp[node][1] = 0;
	for(vi::iterator it = son[node].begin(); it != son[node].end(); ++ it)
	{
		dfs(*it);
		for(int i = p; i >= 1; i --)
		{
			dp[node][i] ++;
			for(int j = 1; j < i; j ++)			
				dp[node][i] = min(dp[node][i], dp[*it][i - j] + dp[node][j]);
		}
	}
}