Submission #261071

#	Time	Username	Problem	Language	Result	Execution time	Memory
261071		atoiz	Beads and wires (APIO14_beads)	C++14	0 / 100	4 ms	4992 KiB

beads

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 200007, INF = 2000000007;
int dp[MAXN][2], N;
vector<pair<int, int>> G[MAXN];

void solve(int u, int p, int c)
{
	int cur[3] = {0, -INF, -INF};
	for (auto e : G[u]) {
		int v = e.first, w = e.second;
		if (v == p) continue;
		solve(v, u, w);
		cur[2] = max(cur[2] + dp[v][0], cur[1] + dp[v][1] + w);
		cur[1] = max(cur[1] + dp[v][0], cur[0] + dp[v][1] + w);
		cur[0] += dp[v][0];
	}
	dp[u][1] = max(cur[0], cur[2]);
	dp[u][0] = max(dp[u][1], cur[1] + c);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N;
	for (int i = 0; i < N - 1; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].emplace_back(v, w);
		G[v].emplace_back(u, w);
	}
	solve(1, 0, 0);
	cout << dp[1][1] << endl;
}

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