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

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

constexpr int N = 514;

int n;
int m;
long long nums[N];
vector<int> tree[N];
int dp[N][N][2];

void dp1 (int now, int dad) {
	dp[now][1][0] = dp[now][1][1] = nums[now];
	for (auto son : tree[now]) {
		if (son == dad) {
			continue;
		}

		dp1 (son, now);

		for (int i = m; i >= 1; i--) {
			for (int j = 1; j <= i; j++) {
				dp[now][i][0] = max (dp[now][i][0], dp[now][i - j][1] + dp[son][j - 1][0]);
				if (j >= 2) {
					dp[now][i][0] = max (dp[now][i][0], dp[son][j - 2][1] + dp[now][i - j][0]);
					dp[now][i][1] = max (dp[now][i][1], dp[son][j - 2][1] + dp[now][i - j][1]);
				}
			}
		}
	}
}

int main () {
	
	freopen ("food.in", "r", stdin);
	freopen ("food.out", "w", stdout);

	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> nums[i];
	}
	int u, v;
	for (int i = 1; i < n; i++) {
		cin >> u >> v;
		tree[u].push_back(v);
		tree[v].push_back(u);
	}

	dp1 (1, 0);

	cout << max (dp[1][m][0], dp[1][m][1]) << endl;
	
	return 0;
}