oj.uz

Submission #848559

# Submission time Handle Problem Language Result Execution time Memory
848559 2023-09-12T22:02:07 Z qthang2k11 Chase (CEOI17_chase) C++17
40 / 100
 274 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[N], 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 pref(x, i) pref[pos_pref[(x)] + (i)]
#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 i = 0, o = g[x].size(); i < o; i++) {
		int y = g[x][i];
		if (i) pref(x, i) = pref(x, i - 1);
		pref(x, i).deal(dp[y], x, 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] = pref(x, (int)g[x].size() - 1);
	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;
		if (i > 0) cur.maxi_(pref(x, i - 1));
		if (i + 1 < o) cur.maxi_(suf(x, i + 1));
		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 65 ms 478560 KB Output is correct
2 Correct 56 ms 478464 KB Output is correct
3 Correct 56 ms 478564 KB Output is correct
4 Correct 57 ms 478548 KB Output is correct
5 Correct 57 ms 478544 KB Output is correct
6 Correct 56 ms 478504 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 478560 KB Output is correct
2 Correct 56 ms 478464 KB Output is correct
3 Correct 56 ms 478564 KB Output is correct
4 Correct 57 ms 478548 KB Output is correct
5 Correct 57 ms 478544 KB Output is correct
6 Correct 56 ms 478504 KB Output is correct
7 Correct 60 ms 481044 KB Output is correct
8 Correct 60 ms 480852 KB Output is correct
9 Correct 58 ms 478576 KB Output is correct
10 Correct 58 ms 478544 KB Output is correct
11 Correct 58 ms 478548 KB Output is correct
12 Correct 56 ms 478548 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 274 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 65 ms 478560 KB Output is correct
2 Correct 56 ms 478464 KB Output is correct
3 Correct 56 ms 478564 KB Output is correct
4 Correct 57 ms 478548 KB Output is correct
5 Correct 57 ms 478544 KB Output is correct
6 Correct 56 ms 478504 KB Output is correct
7 Correct 60 ms 481044 KB Output is correct
8 Correct 60 ms 480852 KB Output is correct
9 Correct 58 ms 478576 KB Output is correct
10 Correct 58 ms 478544 KB Output is correct
11 Correct 58 ms 478548 KB Output is correct
12 Correct 56 ms 478548 KB Output is correct
13 Runtime error 274 ms 524288 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -