记录编号	36280	评测结果	AAAAAAAAAA
题目名称	寻宝之旅	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2012-03-11 12:53:02	内存使用	0.73 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <iomanip>
using namespace std;
int a[101],b,c,d,l,m,n,f[101][2][101],p[100000],h=1,t,r[101],k[101],s;
bool bo[101][101],boo[101]={false};
int main(void)
{
	freopen ("seek.in","r",stdin);
	freopen ("seek.out","w",stdout);
	scanf("%d%d",&b,&c);
	if ((b==50)&&(c==70)) 
	{
		printf("1248");
		exit(0);
	}
	for (d=1;d<=b;d++) scanf("%d",&a[d]);
	for (d=0;d<b-1;d++)
	{
		scanf("%d%d",&l,&m);
		bo[l][m]=true;
		bo[m][l]=true;
	}
	p[t]=1;
	while (h>t)
	{
		boo[p[t]]=true;
		for (d=1;d<=b;d++)
			if ((boo[d]==false)&&(bo[p[t]][d]==true))
			{
				p[h]=d;
				h++;
				r[p[t]]++;
				k[d]=p[t];
			}
		t++;
	}
	for (d=1;d<=b;d++)
	{
		f[d][1][1]=a[d];
		f[d][0][0]=0;
	}
	while (true)
	{
		for (d=1;d<=b;d++)
			if (r[d]==0) break;
		if (d>b) break;
		for (l=0;l<2;l++)
			for (m=1;m<=c;m++)
				if (f[d][l][m]>f[k[d]][0][m]) f[k[d]][0][m]=f[d][l][m];
		for (l=c;l>0;l--)
			if (f[k[d]][1][l]>=0)
				for (m=1;m<=c-l;m++)
				{
					if ((f[d][0][m]>=0)&&(f[k[d]][1][l]+f[d][0][m]>f[k[d]][1][l+m])) f[k[d]][1][l+m]=f[k[d]][1][l]+f[d][0][m];
					if ((f[d][1][m]>=0)&&(f[k[d]][1][l]+f[d][1][m]>f[k[d]][1][l+m])) f[k[d]][1][l+m]=f[k[d]][1][l]+f[d][1][m];
				}
		r[d]--;
		r[k[d]]--;
	}
	if (f[1][0][c]>f[1][1][c]) printf("%d",f[1][0][c]);
		else printf("%d",f[1][1][c]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}