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

#include<stdio.h>
#define max(a,b) a>b?a:b

int n,m,a[101],t[101],v[101][101],f[101][101][2];

bool flag[101];

void swap(int &a,int &b)
{
	int t;
	t=a;a=b;b=t;
}

void dfs(int s)
{
	int i,j,k,Max;
	flag[s]=true;
	for(i=1;i<=t[s];i++)
	{
		if(!flag[v[s][i]])
		{
			dfs(v[s][i]);
			for(j=m;j>0;j--)
			{
				f[s][j][0]=max(f[s][j][0],f[v[s][i]][j][0]);
				f[s][j][0]=max(f[s][j][0],f[v[s][i]][j][1]);
				Max=0;
				for(k=0;k<j;k++)
				{
					Max=max(Max,f[s][j-k][1]+f[v[s][i]][k][0]);
					Max=max(Max,f[s][j-k][1]+f[v[s][i]][k][1]);
				}
				f[s][j][1]=max(f[s][j][1],Max);
			}
		}
	}
}

int main()
{
	freopen("seek.in","r",stdin);
	freopen("seek.out","w",stdout);
	int i,x,y;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		v[x][++t[x]]=y;
		v[y][++t[y]]=x;
	}
	for(i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			f[i][j][1]=a[i];
		}
	}
	dfs(1);
	printf("%d\n",max(f[1][m][0],f[1][m][1]));
	return 0;
}