oj.uz

Submission #848566

# Submission time Handle Problem Language Result Execution time Memory
848566 2023-09-12T22:22:30 Z qthang2k11 Chase (CEOI17_chase) C++17
40 / 100
 238 ms 411984 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) 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) 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);
	if (n <= 1000) dfs_reroot(1, Node());
	cout << ans;
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 320336 KB Output is correct
2 Correct 39 ms 320336 KB Output is correct
3 Correct 37 ms 320336 KB Output is correct
4 Correct 40 ms 320336 KB Output is correct
5 Correct 39 ms 320336 KB Output is correct
6 Correct 40 ms 320596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 320336 KB Output is correct
2 Correct 39 ms 320336 KB Output is correct
3 Correct 37 ms 320336 KB Output is correct
4 Correct 40 ms 320336 KB Output is correct
5 Correct 39 ms 320336 KB Output is correct
6 Correct 40 ms 320596 KB Output is correct
7 Correct 42 ms 322896 KB Output is correct
8 Correct 40 ms 322852 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 Incorrect 238 ms 411984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 320336 KB Output is correct
2 Correct 39 ms 320336 KB Output is correct
3 Correct 37 ms 320336 KB Output is correct
4 Correct 40 ms 320336 KB Output is correct
5 Correct 39 ms 320336 KB Output is correct
6 Correct 40 ms 320596 KB Output is correct
7 Correct 42 ms 322896 KB Output is correct
8 Correct 40 ms 322852 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 Incorrect 238 ms 411984 KB Output isn't correct
14 Halted 0 ms 0 KB -