Submission #321062

#	Time	Username	Problem	Language	Result	Execution time	Memory
321062		jungsnow	Chase (CEOI17_chase)	C++14	0 / 100	368 ms	133348 KiB

chase

#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second

using namespace std;
using ll = long long;

const int maxn = 100001;

typedef pair<ll, ll> ii;

int n, k, a[maxn];
ll up[maxn][101], down[maxn][101], go[maxn], ans = 0;

vector <int> g[maxn];

void dfs(int v, int p = 0) {
	for (int u : g[v]) if (u != p) dfs(u, v);
	down[v][1] = go[v];
	for (int u : g[v]) if (u != p) {
		for (int i = 1; i <= k; ++i) {
			down[v][i] = max(down[v][i], max(down[u][i], down[u][i - 1] + go[v] - a[u]));
			up[v][i] = max(up[v][i], max(up[u][i], up[u][i - 1] + go[v] - a[p]));
			ans = max(ans, down[u][i - 1] + go[v] - a[u]);
			ans = max(ans, up[u][i - 1] + go[v]);
		}
	}
	for (int i = 0; i <= k; ++i) {
		ii mx = ii(0, 0);
		for (int u : g[v]) if (u != p) {
			mx.y = max(mx.y, up[u][i]);
			if (mx.y > mx.x) swap(mx.x, mx.y);
		}
		for (int u : g[v]) if (u != p) {
			ll cur = mx.x; 
			if (up[u][i] == mx.x) cur = mx.y;
			ans = max(ans, cur + down[u][k - i]);
		}
	}
	for (int i = 1; i <= k; ++i) {
		ii mx = ii(0, 0);
		for (int u : g[v]) if (u != p) {
			mx.y = max(mx.y, up[u][i - 1]);
			if (mx.y > mx.x) swap(mx.x, mx.y);
		}
		for (int u : g[v]) if (u != p) {
			ll cur = mx.x; 
			if (up[u][i] == mx.x) cur = mx.y;
			ans = max(ans, cur + down[u][k - i] + go[v] - a[u]);
		}
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) 
		cin >> a[i];
	if (k == 0) {
		cout << 0;
		return 0;
	}
	for (int u, v, i = 1; i < n; ++i) {
		cin >> u >> v;
		g[u].pb(v); g[v].pb(u);
		go[u] += a[v];
		go[v] += a[u];
	}
	dfs(1);
	cout << ans << '\n';
	return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30