记录编号	166490	评测结果	AAAAAAAAAA
题目名称	通往自由的钥匙	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2015-06-15 14:37:17	内存使用	9.66 MiB

#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,p,son[1000],G[1100][1100],vis[1000],f[1111][1111];
struct room
{
	int data,key,l,r,fa;
}T[1051];
void build(int x,int fa)
{
	vis[x]=1;
	T[x].fa=fa;
	if(T[x].fa!=-1)
	{
		if(son[fa]==0)
		{
			T[fa].l=x;
			son[fa]=x;
		}
		else
		{
			T[son[fa]].r=x;
			son[fa]=x;
		}
	}
	for(int i=1;i<=n;++i)
	  if(G[x][i]!=0&&vis[i]==0)
	    build(i,x);
}
int tree_dp(int i,int y)
{
	if(i==-1)return 0;
	if(f[i][y]>0)return f[i][y];	
	int tmp=-1000000;
	tmp=tree_dp(T[i].r,y);
	int yy=y-T[i].data;
	if(yy<0)
	{
		f[i][y]=max(f[i][y],tmp);
		return f[i][y];
	}
	for(int j=0;j<=yy;++j)
	  f[i][y]=max(f[i][y],tree_dp(T[i].l,j)+tree_dp(T[i].r,yy-j)+T[i].key);
    f[i][y]=max(f[i][y],tmp);
    return f[i][y];
}
int main()
{
	freopen("key.in","r",stdin);
	freopen("key.out","w",stdout);
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;++i)
	  T[i].l=T[i].r=-1;
	for(int i=1;i<=n;++i)
	  scanf("%d%d",&T[i].data,&T[i].key);
	for(int i=1;i<=n-1;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		G[x][y]=G[y][x]=1;
	}
	build(1,-1);
	int ans=tree_dp(1,p);
	printf("%d",ans);
	return 0;
}