WA 14 个点

Code:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define inf (1ll << 62)
#define pb push_back
#define PII pair<int , int>
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5 + 10;
int n , k;
vector<int>a(MAXN) , G[MAXN];
vector<vector<vector<ll>>>f(MAXN , vector<vector<ll>>(7 , vector<ll>(2)));
vector<vector<ll>>g(MAXN , vector<ll>(7));
//f[u][i][0] 表示以 u 为根且子树内有 i 条路经，并且 u 不为路径一端点的最大值
//f[u][i][1] 表示以 u 为根且子树内有 i 条路经，并且 u 为路径一端点的最大值

void dfs(int u , int fa) {
	f[u][1][1] = a[u];
	for(auto v : G[u]) {
		if(v == fa) continue;
		dfs(v , u);
		for(int i = k + 1;i >= 1;i --) {
			for(int j = 1;j <= i;j ++) {
				if((i - j == 0 || f[u][i - j][0]) && f[v][j][0]) f[u][i][0] = max(f[u][i][0] , f[v][j][0] + f[u][i - j][0]);
				if((i - j + 1 == 0 || f[u][i - j + 1][1]) && f[v][j][1]) f[u][i][0] = max(f[u][i][0] , f[u][i - j + 1][1] + f[v][j][1]);
				if(f[v][i][1]) f[u][i][1] = max(f[u][i][1] , f[v][i][1] + a[u]);
				if((i - j == 0 || f[u][i - j][1]) && f[v][j][0]) f[u][i][1] = max(f[u][i][1] , f[v][j][0] + f[u][i - j][1]);
				if((i - j == 0 || g[u][i - j]) && f[v][j][1]) f[u][i][1] = max(f[u][i][1] , g[u][i - j] + f[v][j][1]);
			}
		}
		for(int i = 0;i <= k + 1;i ++) {
			g[u][i] = max(g[u][i] , g[v][i]);
		}
	}
	return;
}

inline void solve() {
	cin >> n >> k;
	for(int i = 1;i <= n;i ++) cin >> a[i];
	for(int i = 1;i < n;i ++) {
		int u , v;
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	dfs(1 , 0);
	ll ans = 0;
	for(int i = 0;i <= k;i ++) {
		ans = max(ans , f[1][i][0]);
	}
	cout << ans << "\n";
	return;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin >> t;
	while(t --) solve();
	return 0;
}