oj.uz

Submission #848765

# Submission time Handle Problem Language Result Execution time Memory
848765 2023-09-13T13:07:53 Z qthang2k11 Chase (CEOI17_chase) C++17
100 / 100
 470 ms 331600 KB 
//
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 320536 KB Output is correct
2 Correct 57 ms 320336 KB Output is correct
3 Correct 59 ms 320336 KB Output is correct
4 Correct 57 ms 320336 KB Output is correct
5 Correct 56 ms 320368 KB Output is correct
6 Correct 60 ms 320592 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 320536 KB Output is correct
2 Correct 57 ms 320336 KB Output is correct
3 Correct 59 ms 320336 KB Output is correct
4 Correct 57 ms 320336 KB Output is correct
5 Correct 56 ms 320368 KB Output is correct
6 Correct 60 ms 320592 KB Output is correct
7 Correct 59 ms 320348 KB Output is correct
8 Correct 58 ms 320336 KB Output is correct
9 Correct 57 ms 320336 KB Output is correct
10 Correct 61 ms 320344 KB Output is correct
11 Correct 59 ms 320336 KB Output is correct
12 Correct 62 ms 320368 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 331336 KB Output is correct
2 Correct 414 ms 331524 KB Output is correct
3 Correct 352 ms 326088 KB Output is correct
4 Correct 132 ms 325712 KB Output is correct
5 Correct 410 ms 325936 KB Output is correct
6 Correct 435 ms 325712 KB Output is correct
7 Correct 446 ms 325968 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 320536 KB Output is correct
2 Correct 57 ms 320336 KB Output is correct
3 Correct 59 ms 320336 KB Output is correct
4 Correct 57 ms 320336 KB Output is correct
5 Correct 56 ms 320368 KB Output is correct
6 Correct 60 ms 320592 KB Output is correct
7 Correct 59 ms 320348 KB Output is correct
8 Correct 58 ms 320336 KB Output is correct
9 Correct 57 ms 320336 KB Output is correct
10 Correct 61 ms 320344 KB Output is correct
11 Correct 59 ms 320336 KB Output is correct
12 Correct 62 ms 320368 KB Output is correct
13 Correct 411 ms 331336 KB Output is correct
14 Correct 414 ms 331524 KB Output is correct
15 Correct 352 ms 326088 KB Output is correct
16 Correct 132 ms 325712 KB Output is correct
17 Correct 410 ms 325936 KB Output is correct
18 Correct 435 ms 325712 KB Output is correct
19 Correct 446 ms 325968 KB Output is correct
20 Correct 430 ms 325936 KB Output is correct
21 Correct 131 ms 325712 KB Output is correct
22 Correct 415 ms 325940 KB Output is correct
23 Correct 135 ms 325808 KB Output is correct
24 Correct 442 ms 325940 KB Output is correct
25 Correct 332 ms 325832 KB Output is correct
26 Correct 470 ms 331600 KB Output is correct
27 Correct 453 ms 331380 KB Output is correct