Submission #1043579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043579		EntityPlantt	Beads and wires (APIO14_beads)	C++17	0 / 100	1 ms	5164 KiB

beads

#include <iostream>
#include <vector>
using namespace std;

const int N = 2e5 + 5, INF = 1e7;
// dp[node/subtree][blue pair incomplete?] = sum of blue wires in subtree
int dp[N][2];
vector <pair <int, int>> adj[N];

void dfs(int node, int parent, int pweight) {
	int sum = 0, bestblue = -INF, bestblue2 = -INF, bestblueadd;
	for (auto &[u, w] : adj[node]) {
		if (u == parent) continue;
		dfs(u, node, w);
		sum += dp[u][0];
		if (bestblue <= dp[u][1] - dp[u][0]) {
			bestblue2 = bestblue;
			bestblue = dp[u][1] - dp[u][0];
		}
		else bestblue2 = max(bestblue2, dp[u][1] - dp[u][0]);
	}
	bestblueadd = max(0, bestblue + bestblue2);
	dp[node][0] = max(sum + bestblueadd, sum + pweight + bestblue);
	dp[node][1] = sum + pweight + bestblueadd;
	// cerr << "dp[" << node << "] = {" << dp[node][0] << ", " << dp[node][1] << "}\n";
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	for (int i = 1, u, v, w; i < n; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	dfs(1, 0, 0);
	cout << dp[1][1];
	return 0;
}

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