CVBB ACM Team

POJ 1947

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#define INF 0x3f3f3f3f
using namespace std;
int n,p,res,head[155],cnt,f[155][155];
struct Node{int nxt,to;}Edges[155*2];
void addedge(int u,int v)
{
	Edges[++cnt].nxt=head[u];
	head[u]=cnt,Edges[cnt].to=v;
}
void dfs(int u)
{
	f[u][1]=0;
	for(int i=head[u];~i;i=Edges[i].nxt)
	{
		int v=Edges[i].to;
		if(f[v][1]!=INF)continue;
		dfs(v);
		for(int j=p;j;j--)
		{
			f[u][j]=f[u][j]+1;
			for(int k=0;k<=j;k++)
			{
				f[u][j]=min(f[u][j],f[v][k]+f[u][j-k]);
			}
		}
	}
	if(u!=1)res=min(res,f[u][p]+1);
	else res=min(res,f[u][p]);
}
int main()
{
	while(~scanf("%d%d",&n,&p))
	{
		cnt=0,res=INF;
		memset(head,-1,sizeof(head));
		memset(f,0x3f,sizeof(f));
		for(int i=1;i<n;i++)
		{
			int u,v;
			scanf("%d%d",&u,&v);
			addedge(u,v);
		}
		dfs(1);
		printf("%d\n",res);
	}
	return 0;
}