记录编号	602773	评测结果	AAAAAAAAAA
题目名称	4085.外卖	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	0.358 s
提交时间	2025-07-05 16:49:06	内存使用	4.76 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,m;
int a[N],f[N][N][3];
vector<int> v[N];
void solve(int x,int fa){
	f[x][1][0]=f[x][1][1]=a[x];
	for(int i:v[x]){
		if(i==fa) continue;
		solve(i,x);
		for(int j=m;j>=1;j--){
			for(int k=1;k<=j;k++){
				f[x][j][0]=max(f[x][j][0],f[x][j-k][1]+f[i][k-1][0]);
				if(k>=2){
					f[x][j][0]=max(f[x][j][0],f[i][k-2][1]+f[x][j-k][0]);
					f[x][j][1]=max(f[x][j][1],f[i][k-2][1]+f[x][j-k][1]);
				}
			}
		}
	}
}
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,x,y;i<n;i++){
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	solve(1,0);
	printf("%d\n",max(f[1][m][0],f[1][m][1]));
	return 0;
}