Submission #48295

#	Time	Username	Problem	Language	Result	Execution time	Memory
48295		tmwilliamlin168	Beads and wires (APIO14_beads)	C++11	0 / 100	9 ms	5120 KiB

beads

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define fi first
#define se second

const int mxN=2e5, INF=2e9;
int n, a[mxN];
ll dp[mxN][4];
vector<pii> adj[mxN];

void dfs1(int u, int p) {
	for(pii e : adj[u]) {
		if(e.fi==p)
			continue;
		a[e.fi]=e.se;
		dfs1(e.fi, u);
	}
}

void dfs2(int u, int p) {
	int mi1=-1, mi2=-1;
	for(pii e : adj[u]) {
		if(e.fi==p)
			continue;
		dfs2(e.fi, u);
		dp[u][0]+=max(max(dp[e.fi][0], dp[e.fi][2]), 0LL);
		dp[u][3]+=max(max(dp[e.fi][0], dp[e.fi][1]), max(dp[e.fi][2], 0LL));
		if(mi1==-1||dp[e.fi][3]-max(max(dp[e.fi][0], dp[e.fi][2]), 0LL)>dp[mi1][3]-max(max(dp[mi1][0], dp[mi1][2]), 0LL)) {
			mi2=mi1;
			mi1=e.fi;
		} else if(mi2==-1||dp[e.fi][3]-max(max(dp[e.fi][0], dp[e.fi][2]), 0LL)>dp[mi2][3]-max(max(dp[mi2][0], dp[mi2][2]), 0LL))
			mi2=e.fi;
	}
	dp[u][1]=mi2==-1?-INF:dp[u][0]-max(max(dp[mi1][0], dp[mi1][2]), 0LL)+dp[mi1][3]-max(max(dp[mi2][0], dp[mi2][2]), 0LL)+dp[mi2][3];
	dp[u][2]=mi1==-1?-INF:dp[u][0]-max(max(dp[mi1][0], dp[mi1][2]), 0LL)+dp[mi1][3]+a[u];
	dp[u][3]=max(dp[u][1], dp[u][3])+a[u];
//	cout << dp[u][0] << " " << dp[u][1] << " " << dp[u][2] << " " << dp[u][3] << " " << u << endl;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=0; i<n-1; ++i) {
		int u, v, c;
		cin >> u >> v >> c, --u, --v;
		adj[u].push_back({v, c});
		adj[v].push_back({u, c});
	}
	dfs1(0, -1);
	dfs2(0, -1);
	cout << max(dp[0][0], dp[0][1]);
}

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