Submission #1114592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114592		VectorLi	Beads and wires (APIO14_beads)	C++17	100 / 100	129 ms	43964 KiB

beads

#include <bits/stdc++.h>
#define I64 long long

using namespace std;

const int N = (int) 2E5;
const I64 A = 0 - (I64) 1E18;

int n;
vector<pair<int, int>> e[N];

int p[N];
I64 f[N][2]; 
I64 g[N][2];
vector<I64> a[N], b[N];

void DFS1(int u) {
	if (p[u] >= 0) {
		auto i = e[u].begin();
		while (i -> first != p[u]) {
			i = next(i);
		}
		e[u].erase(i);
	}
	f[u][0] = 0;
	f[u][1] = A;
	for (auto [v, x] : e[u]) {
		p[v] = u;
		DFS1(v);
		f[u][0] = f[u][0] + max(f[v][0], f[v][1] + x);
		f[u][1] = max(f[u][1], f[v][0] + x - max(f[v][0], f[v][1] + x));
	}
	f[u][1] = f[u][1] + f[u][0];
}

void DFS2(int u) {
	int m = (int) e[u].size();
	I64 s = 0;
	a[u] = vector<I64>(m);
	b[u] = vector<I64>(m);
	
	for (auto [v, x] : e[u]) {
		s = s + max(f[v][0], f[v][1] + x);
	}
	for (int i = 0; i < m; i++) {
		int v, x;
		tie(v, x) = e[u][i];
		a[u][i] = f[v][0] + x - max(f[v][0], f[v][1] + x);
		b[u][i] = f[v][0] + x - max(f[v][0], f[v][1] + x);
	}
	for (int i = 0; i < m - 1; i++) {
		a[u][i + 1] = max(a[u][i + 1], a[u][i]);
	}
	for (int i = m - 1; i > 0; i--) {
		b[u][i - 1] = max(b[u][i - 1], b[u][i]);
	}
	
	for (int i = 0; i < m; i++) {
		int v, x;
		tie(v, x) = e[u][i];
		
		I64 t[2];
		t[0] = g[u][0] + s;
		t[0] = t[0] - max(f[v][0], f[v][1] + x);
		t[1] = g[u][1] - g[u][0];
		if (i > 0) {
			t[1] = max(t[1], a[u][i - 1]);
		}
		if (i < m - 1) {
			t[1] = max(t[1], b[u][i + 1]);
		}
		t[1] = t[1] + t[0];
		
		g[v][0] = max(t[0], t[1] + x);
		g[v][1] = t[0] + x;
		DFS2(v);
	}
}

void solve() {
	cin >> n;
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		int x;
		cin >> u >> v >> x;
		u = u - 1;
		v = v - 1;
		e[u].push_back({v, x});
		e[v].push_back({u, x});
	}
	
	p[0] = 0 - 1;
	DFS1(0);
	
	g[0][0] = 0;
	g[0][1] = A;
	DFS2(0);
	
	I64 x = 0;
	for (int u = 0; u < n; u++) {
//		cout << f[u][0] + g[u][0] << "\n";
		x = max(x, f[u][0] + g[u][0]);
	}
	cout << x << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	solve();
	return 0;
}

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