记录编号	602803	评测结果	AAAAAAAAAA
题目名称	4085.外卖	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	0.306 s
提交时间	2025-07-05 19:57:57	内存使用	4.01 MiB

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=505;
int a[N];
int head[N],nxt[N*2],to[N*2],num=0;
void add(int x,int y){
	num++;
	to[num]=y;
	nxt[num]=head[x];
	head[x]=num;
}
int n,k;
int f[N][N][2];
void dfs(int x,int fa){
	f[x][1][0]=f[x][1][1]=a[x];
	for(int z=head[x];z;z=nxt[z]){
		int v=to[z];
		if(v==fa) continue;
		dfs(v,x);
		for(int i=k;i>=1;i--){
			for(int j=1;j<=i;j++){
				f[x][i][0]=max(f[x][i][0],f[x][i-j][1]+f[v][j-1][0]);
				if(j>=2){   
					f[x][i][0]=max(f[x][i][0],f[v][j-2][1]+f[x][i-j][0]);
					f[x][i][1]=max(f[x][i][1],f[v][j-2][1]+f[x][i-j][1]);
				}
			}
		}
	}
}
int main(){
	cin>>n>>k; 
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n-1;i++){
	    int u,v;
	    cin>>u>>v;
	    add(u,v);
	    add(v,u);
	}
	dfs(1,0);
	cout<<max(f[1][k][0],f[1][k][1])<<endl;
	return 0;
}