记录编号	597517	评测结果	AAAAAAAAAA
题目名称	外卖	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.353 s
提交时间	2024-11-28 19:47:17	内存使用	4.28 MiB

#include<bits/stdc++.h>
using namespace std;
int n,m,a[510],tot,h[510],v[1010],ne[1010],f[510][510][2],siz[510],ans;
void add(int x,int y)
{
	tot++;
	v[tot]=y;
	ne[tot]=h[x];
	h[x]=tot;
}
void dp(int x,int fa)
{
	siz[x]=1; 
	f[x][1][0]=a[x]; 
	f[x][1][1]=a[x];
	for(int i=h[x];i;i=ne[i])
	{
		int y=v[i];
		if(y==fa) continue;
		dp(y,x); 
		siz[x]+=siz[y];
		for(int j=m;j;j--)
		{
			for(int k=1;k<j;k++)
			{
				if(j-k-2>=0) 
				{
					f[x][j][0]=max(f[x][j][0],f[y][k][0]+f[x][j-k-2][0]);
					f[x][j][1]=max(f[x][j][1],f[y][k][0]+f[x][j-k-2][1]);
				}
				f[x][j][1]=max(f[x][j][1],f[y][k][1]+f[x][j-k-1][0]);
			}
		}
		
	}
		
}
int main()
{
	freopen("food.in","r",stdin);
	freopen("food.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	} 
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dp(1,0);
	for(int i=1;i<=m;i++)
	{
		ans=max(ans,max(f[1][i][0],f[1][i][1]));
	} 
	printf("%d",ans);
	return 0;
}