记录编号	602745	评测结果	AAAAAAAAAA
题目名称	4085.外卖	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	0.391 s
提交时间	2025-07-05 16:22:02	内存使用	7.26 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
int f[N][2 * N][2], a[N];
vector<int> adj[N];
int n, k;
void dp(int x, int fa) {
    f[x][1][0] = f[x][1][1] = a[x];
    for (int z = 0; z < adj[x].size(); ++z) {
        int y = adj[x][z];
        if (y == fa) continue;
        dp(y, 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[y][j - 1][0]);
                if (j >= 2) {
                    f[x][i][0] = max(f[x][i][0], f[y][j - 2][1] + f[x][i - j][0]);
                    f[x][i][1] = max(f[x][i][1], f[y][j - 2][1] + f[x][i - j][1]);
                }
            }
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    while (cin >> n >> k) {
        memset(a, 0, sizeof(a));
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; ++i) adj[i].clear();
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i < n; ++i) {
            int x, y;
            cin >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        dp(1, 0);
        cout << max(f[1][k][0], f[1][k][1]) << endl;
    }
    return 0;
}