记录编号	166595	评测结果	AAAAAAAAAA
题目名称	通往自由的钥匙	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.010 s
提交时间	2015-06-15 18:05:01	内存使用	0.49 MiB

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
int yao[150],lian[150][150],mo[150];
int n,p,gs[150],f[150][150];
bool b[150];
void dp(int);
int main()
{   //memset(lian,-1,sizeof(lian));
    freopen("key.in","r",stdin);
	freopen("key.out","w",stdout);
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;++i)
	{   
		scanf("%d%d",&mo[i],&yao[i]);
	}
	for(int i=1;i<n;++i)
	{   int k,l;
		scanf("%d%d",&k,&l);
		lian[k][++gs[k]]=l;
		lian[l][++gs[l]]=k;//必须建双向边，因为还有可能回去；
	}
	int maxx=0;
	dp(1);
	for(int i=1;i<=p;++i)
	    maxx=max(maxx,f[1][i]);
	printf("%d",maxx);
	//system("pause");
}
void dp(int y)
{
	b[y]=1;
	for(int i=1;i<=gs[y];++i)
	{
		int yu=lian[y][i];
		//cout<<yu<<" ";
		if(b[yu])
		  continue;//如果已经访问，则找其他边；
		dp(yu);
		for(int j=p;j>=0;--j)
		 for(int ju=0;ju<=j;++ju)
		  if(f[y][j]<f[y][j-ju]+f[yu][ju])
		   f[y][j]=f[y][j-ju]+f[yu][ju];//当前节点耗费j-ju个魔法值，与其相连的那个点消耗ju个魔法值；
	}
	for(int i=p;i>=mo[y];--i)
	 f[y][i]=f[y][i-mo[y]]+yao[y];
	for(int i=mo[y]-1;i>=0;--i)
	 f[y][i]=0;//如果剩余魔法值小于当前根的魔法值，则为0；；
	return;
}