Submission #848765

#	Time	Username	Problem	Language	Result	Execution time	Memory
848765		qthang2k11	Chase (CEOI17_chase)	C++17	100 / 100	470 ms	331600 KiB

chase

//
#include <bits/stdc++.h>
using namespace std;

// #ifdef LOCAL
// #define fprintf(...) {}
// #endif
 
using ll = long long;
 
const int N = 1e5 + 5;
 
template<class X, class Y>
inline void maxi(X &x, Y y) {
	if (x < y) x = y;
}
 
vector<int> g[N];
int n, k, a[N];
ll s[N];
 
ll ans = 0, INF;

ll up[N][101][2], down[N][101][2], sdown[101][2];
int par[N];

void dfs_init(int x, int p) {
	par[x] = p;
	for (int i = g[x].size() - 1; i >= 0; i--) {
		int y = g[x][i];
		if (y != p) continue;
		swap(g[x][i], g[x].back());
		g[x].pop_back();
	}
	for (int y: g[x]) dfs_init(y, x);
}
 
void dfs(int x) {
	up[x][0][0] = down[x][0][0] = 0;
	if (k > 0) {
		up[x][1][1] = s[x];
		down[x][1][0] = s[x] - a[par[x]];
		if (k > 1) down[x][1][1] = s[x] - a[par[x]];
	}
	for (int y: g[x]) {
		dfs(y);
		memset(sdown, -63, sizeof sdown);
		for (int i = 0; i <= k; i++) {
			for (int j = 0; j < 2; j++) {
				sdown[i][j] = down[y][i][j];
				if (i) maxi(sdown[i][j], sdown[i - 1][j]);
			}
		}
		for (int i = 0; i <= k; i++) {
			for (int j = 0; j < 2; j++) {
				maxi(ans, up[x][i][j] + sdown[k - i][j]);
				// if (up[x][i][j] + sdown[k - i][j] == 24) {
					// fprintf(stderr, "at up[%d][%d][%d] = %lld and sdown[%d][%d][%d] = %lld\n", x, i, j, up[x][i][j], y, k - i, j, sdown[k - i][j]);
				// }
			}
		}
		for (int i = 0; i <= k; i++) {
			for (int j = 0; j < 2; j++) {
				ll cur = up[y][i][j];
				if (i < k) maxi(up[x][i + 1][1], cur + s[x] - a[y]);
				maxi(up[x][i][0], cur);
			}
		}
		for (int i = 0; i <= k; i++) {
			if (i < k) {
				maxi(down[x][i + 1][1], down[y][i][1] + s[x] - a[par[x]]);
				maxi(down[x][i + 1][0], down[y][i][1] + s[x] - a[par[x]]);
			}
			maxi(down[x][i][1], down[y][i][0]);
			maxi(down[x][i][0], down[y][i][0]);
		}
	}
	for (int i = 0; i <= k; i++) {
		for (int j = 0; j < 2; j++)
			maxi(ans, up[x][i][j]);
		maxi(ans, down[x][i][0]);
	}
	// for (int i = 0; i <= k; i++)
		// for (int j = 0; j < 2; j++)
			// fprintf(stderr, "down[%d][%d][pre choose? %d] = %lld\n", x, i, j, down[x][i][j])/*,
			// fprintf(stderr, "up[%d][%d][%d] = %lld\n", x, i, j, up[x][i][j])*/;
	reverse(g[x].begin(), g[x].end());
}
 
int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> k;
	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].emplace_back(y);
		g[y].emplace_back(x);
	}
	for (int x = 1; x <= n; x++) {
		for (int y: g[x])
			s[x] += a[y];
	}
	dfs_init(1, 0);
	memset(up, -63, sizeof up);
	memset(down, -63, sizeof down);
	dfs(1);
	memset(up, -63, sizeof up);
	memset(down, -63, sizeof down);
	dfs(1);
	cout << ans;
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30