记录编号	602650	评测结果	AAAAAAAAAA
题目名称	4085.外卖	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.058 s
提交时间	2025-07-05 13:26:59	内存使用	4.46 MiB

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAXN = 505;
const int INF = 1e9;

int n, m;
int a[MAXN];
vector<int> tree[MAXN];
int dp[MAXN][MAXN][2];
int sz[MAXN];

void dfs(int u, int fa){
    sz[u] = 1;
    dp[u][1][0] = dp[u][1][1] = a[u];
    for(int v : tree[u]){
        if(v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
        for(int t = min(m, 3 * sz[u]);t >= 1;t --){
            for(int k = 1; k <= min(t - 1, 3 * sz[v]);k ++){
                if(t - k >= 2){
                    dp[u][t][0] = max(dp[u][t][0], dp[v][k][0] + dp[u][t - k - 2][0]);
                    dp[u][t][1] = max(dp[u][t][1], dp[v][k][0] + dp[u][t - k - 2][1]);
                }
                dp[u][t][1] = max(dp[u][t][1], dp[v][k][1] + dp[u][t - k - 1][0]);
            }
        }
    }
}

int main(){
	freopen("food.in","r",stdin);
	freopen("food.out","w",stdout);
    cin.tie(0) -> ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1;i <= n;i ++) cin >> a[i];
    for (int i = 1;i < n;i ++){
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= n;j ++){
			for(int k = 1;k <= n;k ++){
				dp[i][j][k] = -INF;
			}
		}
	}
    dfs(1, -1);
    int ans = 0;
    for(int t = 1;t <= m;t ++){
        ans = max(ans, max(dp[1][t][0], dp[1][t][1]));
    }
    cout << ans << '\n';
    return 0;
}