Submission #1211290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211290		k1r1t0	Beads and wires (APIO14_beads)	C++20	100 / 100	119 ms	29108 KiB

beads

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 210000;
const int INF = (int)(1e18);

int dp[N][2], n, a[N], b[N], c[N], ans;
vector<array<int, 2>> g[N];

void build(int v, int p = -1, int pw = 0) {
	for (auto [u, w] : g[v]) if (u != p) {
		build(u, v, w);
		dp[v][0] += dp[u][1];
	}
	dp[v][1] = -INF;
	for (auto [u, w] : g[v]) if (u != p)
		dp[v][1] = max(dp[v][1], dp[v][0] - dp[u][1] + dp[u][0] + w);
	dp[v][1] = max(dp[v][1] + pw, dp[v][0]);
}

void solve(int v, int p = -1) {
	int dp0 = 0;
	for (auto [u, w] : g[v])
		dp0 += dp[u][1];
	int m = g[v].size();
	vector<int> dp1(m, -INF);
	int val = -INF;
	for (int i = 0; i < m; i++) {
		dp1[i] = max(dp1[i], val);
		auto [u, w] = g[v][i];
		val = max(val, dp0 - dp[u][1] + dp[u][0] + w);
	}
	val = -INF;
	for (int i = m - 1; i >= 0; i--) {
		dp1[i] = max(dp1[i], val);
		auto [u, w] = g[v][i];
		val = max(val, dp0 - dp[u][1] + dp[u][0] + w);
	}
	for (int i = 0; i < m; i++) {
		auto [u, w] = g[v][i];
		dp[v][0] = dp0 - dp[u][1];
		dp[v][1] = max(dp1[i] - dp[u][1] + w, dp0 - dp[u][1]);
		if (u != p) solve(u, v);
	}
	ans = max(ans, dp0);
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		cin >> a[i] >> b[i] >> c[i];
		g[a[i]].push_back({b[i], c[i]});
		g[b[i]].push_back({a[i], c[i]});
	}
	build(1);
	solve(1);
	cout << ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43