oj.uz

Submission #321062

# Submission time Handle Problem Language Result Execution time Memory
321062 2020-11-10T19:46:59 Z jungsnow Chase (CEOI17_chase) C++14
0 / 100
 368 ms 133348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 368 ms 133348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2668 KB Output isn't correct
2 Halted 0 ms 0 KB -