记录编号	600587	评测结果	AAAAAAAAAA
题目名称	外卖	最终得分	100
用户昵称	zjzhe	是否通过	通过
代码语言	C++	运行时间	0.063 s
提交时间	2025-05-08 14:04:48	内存使用	4.13 MiB

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=515;
int n,m,a[N],f[N][N][2],siz[N];
vector<int>lk[N];
void dfs(int u,int fa){
    siz[u]=1,f[u][1][0]=f[u][1][1]=a[u];
    for(int v:lk[u]){
        if(v==fa)continue;
        dfs(v,u);siz[u]+=siz[v];
        for(int i=min(m,3*siz[u]);i>=1;i--){// 在一个子树内最多花3*siz时间
            for(int j=1;j<min(i,3*siz[v]);j++){
                if(i-j-2>=0){
                    f[u][i][1]=max({f[u][i][1],f[v][j][1]+f[u][i-j-2][1]});// 去和回各消耗1时间所以-2
                    f[u][i][0]=max(f[u][i][0],f[v][j][1]+f[u][i-j-2][0]);
                }
                f[u][i][0]=max(f[u][i][0],f[v][j][0]+f[u][i-j-1][1]);// 去了不用回所以-1
            }
        }
    }
}
#undef int
int main(){
#define int long long
    freopen("food.in","r",stdin);
    freopen("food.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		lk[x].push_back(y),lk[y].push_back(x);
	}
    int ans=0;dfs(1,0);
    for(int i=1;i<=m;i++)ans=max({ans,f[1][i][0],f[1][i][1]});
    cout<<ans;
    return 0;
}