oj.uz

Submission #848519

# Submission time Handle Problem Language Result Execution time Memory
848519 2023-09-12T20:19:36 Z qthang2k11 NLO (COCI18_nlo) C++17
0 / 110
 28 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#undef LOCAL
#endif

#ifndef 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;

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] + (j ? a[y] : 0));
				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 + 1][1], cur + s[x] - a[y] - (j ? a[x] : 0));
				}
				// maxi(val[i][0], cur + (j ? a[y] : 0));
				maxi(val[i][0], cur/* + (j ? a[x] : 0)*/);
			}
		}
	}

	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] + (j ? a[y] : 0));
				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 + 1][1], cur + s[x] - a[y] - (j ? a[x] : 0));
				}
				// maxi(ans.val[i][0], cur + (j ? a[y] : 0));
				maxi(ans.val[i][0], cur/* + (j ? a[x] : 0)*/);
			}
		}
		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;
	}

	void debug(int x) {
		#ifndef LOCAL
		return;
		#endif
		cerr << string(15, '=') << '\n';
		for (int i = 0; i <= k; i++)
			for (int j = 0; j < 2; j++)
				fprintf(stderr, "dp[%d][%d][%d] = %lld\n", x, i, j, val[i][j]);
		cerr << string(15, '=') << '\n';
	}
};

vector<Node> pref[N], suf[N];
Node dp[N];

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);
}

void dfs(int x) {
	pref[x].resize(g[x].size());
	suf[x].resize(g[x].size());
	for (int y: g[x]) dfs(y);
	for (int i = 0, o = g[x].size(); i < o; i++) {
		int y = g[x][i];
		auto &p = pref[x][i];
		if (i) p.maxi_(pref[x][i - 1]);
		p.deal(dp[y], x, y);
	}
	for (int o = g[x].size(), i = o - 1; i >= 0; i--) {
		int y = g[x][i];
		auto &p = suf[x][i];
		if (i < o - 1) p.maxi_(suf[x][i + 1]);
		p.deal(dp[y], x, y);
	}
	if (!g[x].empty()) dp[x] = pref[x].back();
	// else {
		maxi(dp[x].val[0][0], 0);
		if (k > 0) maxi(dp[x].val[1][1], s[x]);
	// }
	maxi(ans, dp[x].res());
	dp[x].debug(x);
}

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() {
#ifndef LOCAL
	cin.tie(0)->sync_with_stdio(0); // ====================================================
#endif
//	freopen("chase.03.01.in", "r", stdin);
	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];
		fprintf(stderr, "s[%d] = %lld\n", x, s[x]);
	}
//	cerr << "?\n";
	dfs_init(1, 0);
//	cerr << "?\n";
	// return 0;
	dfs(1);
//	cerr << "?\n";
	dfs_reroot(1, Node()); // ============================================================
//	cerr << "?\n";
	cout << ans;
	return 0;
}

Subtask #1
0 / 110.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 65536 KB Execution killed with signal 9
2 Runtime error 13 ms 65536 KB Execution killed with signal 9
3 Runtime error 13 ms 65536 KB Execution killed with signal 9
4 Runtime error 13 ms 65536 KB Execution killed with signal 9
5 Runtime error 11 ms 65536 KB Execution killed with signal 9
6 Runtime error 14 ms 65536 KB Execution killed with signal 9
7 Runtime error 28 ms 65536 KB Execution killed with signal 9
8 Runtime error 14 ms 65536 KB Execution killed with signal 9
9 Runtime error 11 ms 65536 KB Execution killed with signal 9
10 Runtime error 13 ms 65536 KB Execution killed with signal 9