记录编号	602662	评测结果	AAAAAAAAAA
题目名称	4085.外卖	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	0.086 s
提交时间	2025-07-05 13:31:49	内存使用	4.65 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n,m;
ll a[1000],head[2000],nxt[2000],to[2000],cnt,s[2000];
ll f[1000][1000][2],ans;

void add(ll x,ll y){
	to[++cnt]=y;
	nxt[cnt]=head[x];
	head[x]=cnt;
	to[++cnt]=x;
	nxt[cnt]=head[y];
	head[y]=cnt;
}

void dp(ll u,ll fa){
	s[u]=1;f[u][1][0]=a[u];f[u][1][1]=a[u];
	for (int i=head[u];i;i=nxt[i]){
		ll v=to[i];
		if (v!=fa){
			dp(v,u);
			s[u]+=s[v];
			for (int j=min(m,3*s[u]);j;j--){
				for (int k=1;k<min((ll)j,3*s[v]);k++){
					if (j-k-2>=0){
						f[u][j][0]=max(f[u][j][0],f[v][k][0]+f[u][j-k-2][0]);
						f[u][j][1]=max(f[u][j][1],f[v][k][0]+f[u][j-k-2][1]);
					}
					f[u][j][1]=max(f[u][j][1],f[v][k][1]+f[u][j-k-1][0]);
				}
			}
		}
	}
	
}


int main(){
	freopen("food.in","r",stdin);
	freopen("food.out","w",stdout);
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	scanf("%lld %lld",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for (int i=1;i<n;i++){
		ll x,y;
		scanf("%lld %lld",&x,&y);
		add(x,y);
	}
	dp(1,0);
	for (int i=1;i<=m;i++) ans=max(ans,max(f[1][i][0],f[1][i][1]));
	printf("%lld\n",ans);
	return 0;
}