记录编号	118452	评测结果	AAAAAAAAAAAAAA
题目名称	重建道路	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.038 s
提交时间	2014-09-06 22:32:39	内存使用	0.38 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

vector<int> G[155];
int n,p,x,y,id[155]={0};
int f[155][155]={0}; //以i为根取j个点的最小值 

void dp(int x){
	f[x][1]=0;
	for(int i=0;i<G[x].size();i++)
	{
		dp(G[x][i]);
		for(int j=p;j>=1;j--)
		{
			f[x][j]++; //如果彻底不考虑这个子树的话，就要把它剪掉
			for(int k=1;k<j;k++)
			{
				f[x][j]=min(f[x][j],f[G[x][i]][j-k]+f[x][k]);
			}
		}
	}
}

void init(){
	freopen("reroads.in","r",stdin);
	freopen("reroads.out","w",stdout);
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=p;j++)
		{
			f[i][j]=100001;
		}
	} 
	for(int i=1;i<n;i++)
	{
		cin>>x>>y;
		id[y]++;
		G[x].push_back(y);
	}
	for(int i=1;i<=n;i++)
	{
		if(id[i]==0) //如果i为根，开始 
		{
			dp(i);
			int ans=f[i][p]; //根开始
			for(int i=1;i<=n;i++)
				ans=min(ans,f[i][p]+1); //之所以加1因为要除去跟 
			cout<<ans<<endl;
			break;
		}
	}
}

int main(){
	init();
	return 0;
}

/*
11 6
1 2
1 3
1 4
1 5
2 6
2 7
2 8
4 9
4 10
4 11
*/