记录编号	602693	评测结果	AAAAAAAAAA
题目名称	4085.外卖	最终得分	100
用户昵称	汐汐很希希	是否通过	通过
代码语言	C++	运行时间	0.319 s
提交时间	2025-07-05 15:03:06	内存使用	4.64 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=510;
int n,m;
int a[N],f[N][2*N][2];
vector<int> g[N];
void dp(int x,int fa)
{
    f[x][1][0]=f[x][1][1]=a[x];
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i];
        if(y==fa) continue;
        dp(y,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[y][k-1][0]);
                if(k>=2)
                {
                    f[x][j][0]=max(f[x][j][0],f[y][k-2][1]+f[x][j-k][0]);
                    f[x][j][1]=max(f[x][j][1],f[y][k-2][1]+f[x][j-k][1]);
                }
            }
        }
    }
}
int main()
{
    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;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dp(1,0);
    int ans=max(f[1][m][0],f[1][m][1]);
    cout<<ans<<endl;
    return 0;
}