Submission #45264

#	Time	Username	Problem	Language	Result	Execution time	Memory
45264		qoo2p5	Chase (CEOI17_chase)	C++17	100 / 100	625 ms	264928 KiB

chase

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

const int N = (int) 1e5 + 123;
const int CNT = 101;

int n, cc;
vector<int> g[N];
ll p[N], around[N];
ll up[N][CNT], down[N][CNT][2];
ll ans;
ll best_up[CNT], best_strange[CNT];

void dfs(int v, int f = 0) {
	maxi(up[v][1], around[v]);
	maxi(down[v][1][1], around[v]);
	
	int ptr = -1;
	int id = 0;
	for (int u : g[v]) {
		if (u == f) {
			ptr = id;
			id++;
			continue;
		}
		dfs(u, v);
		id++;
	}
	if (ptr != -1) {
		g[v].erase(g[v].begin() + ptr);
	}
	
	for (int u : g[v]) {
		rep(i, 1, cc + 1) {
			maxi(up[v][i], up[u][i]);
			maxi(up[v][i], up[u][i - 1] + around[v] - p[u]);
			maxi(down[v][i][0], max(down[u][i][0], down[u][i][1] - p[v]));
			maxi(down[v][i][1], max(down[u][i - 1][0] + around[v], down[u][i - 1][1] - p[v] + around[v]));
		}
	}
	
	rep(i, 1, cc + 1) {
		maxi(up[v][i], up[v][i - 1]);
		rep(j, 0, 2) {
			maxi(down[v][i][j], down[v][i - 1][j]);
		}
	}
	maxi(ans, up[v][cc]);
	maxi(ans, max(down[v][cc][0], down[v][cc][1]));
	
	rep(iter, 0, 2) {
		rep(i, 0, cc + 1) {
			best_up[i] = -LINF;
			best_strange[i] = -LINF;
		}
		for (int u : g[v]) {
			rep(i, 1, cc + 1) {
				maxi(ans, down[u][i][0] + best_up[cc - i]);
				maxi(ans, down[u][i][1] - p[v] + best_up[cc - i]);
				maxi(ans, down[u][i - 1][0] + best_strange[cc - i] + around[v]);
				maxi(ans, down[u][i - 1][1] - p[v] + best_strange[cc - i] + around[v]);
			}
			
			rep(i, 1, cc + 1) {
				maxi(best_up[i], up[u][i]);
				maxi(best_up[i], best_up[i - 1]);
				maxi(best_strange[i], up[u][i] - p[u]);
				maxi(best_strange[i], best_strange[i - 1]);
			}
		}
		reverse(all(g[v]));
	}
}

void run() {
	cin >> n >> cc;
	rep(i, 1, n + 1) {
		cin >> p[i];
	}
	rep(i, 0, n - 1) {
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	rep(i, 1, n + 1) {
		for (int j : g[i]) {
			around[i] += p[j];
		}
	}
	
	dfs(1);
	cout << ans << "\n";
}

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