Submission #235682

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

beads

#include <bits/stdc++.h>
#define norope first
#define v first
#define rope second
#define w second
#define all(x) x.begin(), x.end()
using namespace std;
typedef pair<long long, long long> ii;
const long long inf = 1023456789012345;
vector<ii> adj[200005];

///norope, red edge to parent is normal
///rope, blue edge to parent is normal
///norope, blue edge to parent is normal
///each node can only have <= 2 special edges from children.
///if 1 special, then node is rope. if 0 or 2, then is norope

ii dfs(int u, int p){
	vector<long long> specialDifference = {-inf, -inf};
	long long sumNormal = 0;
	
	for(ii e : adj[u]){
		if(e.v == p) continue;
		ii res = dfs(e.v, u);
		
		long long normal = max(e.w + res.rope, res.norope);
		long long special = e.w + res.norope;
				
		sumNormal += normal;
		specialDifference.push_back(special - normal);
	}
	
	sort(all(specialDifference), greater<long long>());
	
	ii ans;
	ans.norope = max(sumNormal + specialDifference[0] + specialDifference[1], sumNormal);
	ans.rope = sumNormal + specialDifference[0];
	
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);
	
	int n; cin >> n;
	for(int i = 1;i < n;i++){
		int u, v, w; cin >> u >> v >> w;
		adj[u].push_back(ii(v,w));
		adj[v].push_back(ii(u,w));
	}
	
	cout << dfs(1,0).norope;
}

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