oj.uz

Submission #848565

# Submission time Handle Problem Language Result Execution time Memory
848565 2023-09-12T22:20:12 Z qthang2k11 Chase (CEOI17_chase) C++17
40 / 100
 396 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
 
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;
 
struct Node {
	ll val[101][2];
 
	Node() {
		memset(val, -63, sizeof val);
	}
 
	void maxi_(const Node &other) {
		for (int i = 0; i <= k; i++)
			for (int j = 0; j < 2; j++)
				maxi(val[i][j], other.val[i][j]);
	}
 
	void deal(const Node &other, const int &x, const int &y) { // update from y to x
		for (int i = 0; i <= k; i++) {
			for (int j = 0; j < 2; j++) {
				ll cur = other.val[i][j];
				if (i < k) {
					if (j) maxi(val[i + 1][1], cur + s[x] - a[y]);
					else maxi(val[i + 1][1], cur + s[x] - a[y]);
				}
				maxi(val[i][0], cur);
			}
		}
	}
 
	Node deal_(const int &x, const int &y) { // update from y to x
		Node ans;
		for (int i = 0; i <= k; i++) {
			for (int j = 0; j < 2; j++) {
				ll cur = val[i][j];
				if (i < k) {
					if (j) maxi(ans.val[i + 1][1], cur + s[x] - a[y]);
					else maxi(ans.val[i + 1][1], cur + s[x] - a[y]);
				}
				maxi(ans.val[i][0], cur);
			}
		}
		return ans;
	}
 
	ll res() const {
		ll ans = 0;
		for (int i = 0; i <= k; i++)
			for (int j = 0; j < 2; j++)
				maxi(ans, val[i][j]);
		return ans;
	}
};
 
Node dp[N], pref, suf[N];
int pos_pref[N];
 
int tcur = 0;
 
void dfs_init(int x, int 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);
}

#define suf(x, i) suf[pos_pref[(x)] + (i)]
 
void dfs(int x) {
	pos_pref[x] = ++tcur;
	tcur += g[x].size() - 1;
	for (int y: g[x]) dfs(y);
	for (int o = g[x].size(), i = o - 1; i >= 0; i--) {
		int y = g[x][i];
		if (i < o - 1) suf(x, i) = suf(x, i + 1);
		suf(x, i).deal(dp[y], x, y);
	}
	if (!g[x].empty()) dp[x] = suf(x, 0);
	pref = Node();
	for (int i = 0, o = g[x].size(); i < o - 1; i++) {
		int y = g[x][i];
		suf(x, i) = suf(x, i + 1);
		if (i) suf(x, i).maxi_(pref);
		pref.deal(dp[y], x, y);
	}
	if (!g[x].empty()) suf(x, (int)g[x].size() - 1) = pref;
	maxi(dp[x].val[0][0], 0);
	if (k > 0) maxi(dp[x].val[1][1], s[x]);
	maxi(ans, dp[x].res());
}
 
void dfs_reroot(int x, Node down) {
	maxi(down.val[0][0], 0);
	if (k > 0) maxi(down.val[1][1], s[x]);
	maxi(ans, down.res());
	for (int i = 0, o = g[x].size(); i < o; i++) {
		int y = g[x][i];
		Node cur = down;
		cur.maxi_(suf(x, i));
		dfs_reroot(y, cur.deal_(y, x));
	}
}
 
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);
	dfs(1);
	dfs_reroot(1, Node());
	cout << ans;
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 320336 KB Output is correct
2 Correct 38 ms 320340 KB Output is correct
3 Correct 37 ms 320336 KB Output is correct
4 Correct 39 ms 320336 KB Output is correct
5 Correct 38 ms 320340 KB Output is correct
6 Correct 38 ms 320308 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 320336 KB Output is correct
2 Correct 38 ms 320340 KB Output is correct
3 Correct 37 ms 320336 KB Output is correct
4 Correct 39 ms 320336 KB Output is correct
5 Correct 38 ms 320340 KB Output is correct
6 Correct 38 ms 320308 KB Output is correct
7 Correct 43 ms 322740 KB Output is correct
8 Correct 41 ms 322740 KB Output is correct
9 Correct 39 ms 320336 KB Output is correct
10 Correct 40 ms 320336 KB Output is correct
11 Correct 39 ms 320336 KB Output is correct
12 Correct 39 ms 320336 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 396 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 320336 KB Output is correct
2 Correct 38 ms 320340 KB Output is correct
3 Correct 37 ms 320336 KB Output is correct
4 Correct 39 ms 320336 KB Output is correct
5 Correct 38 ms 320340 KB Output is correct
6 Correct 38 ms 320308 KB Output is correct
7 Correct 43 ms 322740 KB Output is correct
8 Correct 41 ms 322740 KB Output is correct
9 Correct 39 ms 320336 KB Output is correct
10 Correct 40 ms 320336 KB Output is correct
11 Correct 39 ms 320336 KB Output is correct
12 Correct 39 ms 320336 KB Output is correct
13 Runtime error 396 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -