Submission #1166093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166093		Gurban	Beads and wires (APIO14_beads)	C++17	100 / 100	123 ms	17336 KiB

beads

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

using ll = long long;

const int inf = 1e9;

const int maxn=2e5+5;
int n,ans;
int dp[maxn][2];
vector<pair<int,int>>E[maxn];

void dfs(int nd,int par){
	dp[nd][0] = 0;
	dp[nd][1] = -inf;

	int md = -inf;

	for(auto i : E[nd]){
		int to = i.first;
		int w = i.second;
		if(to != par){
			dfs(to,nd);
			
			int gain = max(dp[to][0], dp[to][1] + w);
			dp[nd][0] += gain;
		
			md = max(md, dp[to][0] + w - gain);
		}

	}

	if(md != -inf){
		dp[nd][1] = dp[nd][0] + md;
	}
}

void calc(int nd,int par, pair<int,int>dp_par){

	
	int ch1 = -inf;
	int ch2 = -inf;

	int jog = 0;

	for(auto i : E[nd]){
		int to = i.first;
		int w = i.second;
		
		int gain;
		int ch;

		if(to == par){
			gain = max(dp_par.first, dp_par.second + w);
			ch = dp_par.first + w - gain;
		}
		else {
			gain = max(dp[to][0], dp[to][1] + w);
			ch = dp[to][0] + w - gain;
		}
		
		jog += gain;
		if(ch > ch1){
			ch2 = ch1;
			ch1 = ch;
		}
		else if(ch > ch2){
			ch2 = ch;
		}
	}	

	ans = max(ans,jog);

	for(auto i : E[nd]){
		int to = i.first;
		int w = i.second;

		if(to == par) continue;
		
		int gain = max(dp[to][0], dp[to][1] + w);
		int ch = dp[to][0] + w - gain;

		if(ch1 == ch){
			calc(to,nd, {jog-gain,jog-gain+ch2});
		}
		else calc(to,nd, {jog-gain,jog-gain+ch1});
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for(int i = 1;i < n;i++){
		int x,y,w;
		cin >> x >> y >> w;
		E[x].push_back({y,w});
		E[y].push_back({x,w});
	}

	
	dfs(1,0);

	calc(1,0,{0,-inf});

	cout<<ans;
}

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