제출 #235682

#제출 시각아이디문제언어결과실행 시간메모리
235682oolimry구슬과 끈 (APIO14_beads)C++14
0 / 100
7 ms4992 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...