Submission #23530

#	Time	Username	Problem	Language	Result	Execution time	Memory
23530		Ali_Sh	Beads and wires (APIO14_beads)	C++14	0 / 100	22 ms	23936 KiB

beads

#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define ll long long
#define int long long

using namespace std ;

const int MAXN = 1001 * 1001 ; 

vector<pair<int,int>> adj[MAXN] ; 

int dp[MAXN] , pd[MAXN] ; 

void dfs(int u , int p)
{
	dp[u] = 0 ; 
	pd[u] = -1e17 ; 
	vector<pair<int,int>> child  ; 
	for(auto v : adj[u])
	{
		if(v.F==p) continue ;
		dfs(v.F,u) ; 
		child.pb(v) ; 
	}
	if(!child.size()) return ; 
	
	if(child.size()==1)
	{
		int v = child[0].F , w = child[0].S ; 
		pd[u] = w + dp[v] ; 
		dp[u] = max(dp[v],w+pd[v]) ; 
		return ; 
	}
	int sum = 0 ; 
	for(auto v : child) sum += max(dp[v.F],v.S+pd[v.F]) ; 
	for(auto v : child) pd[u] = max(pd[u],sum-max(dp[v.F],v.S+pd[v.F])+v.S+dp[v.F]) ; 
	
	dp[u] = sum ; 
	vector<int> val ; 
	for(auto v : child)
	{
		val.pb(v.S+dp[v.F]-max(dp[v.F],v.S+pd[v.F])) ; 
	}
	sort(val.rbegin(),val.rend()) ; 
	dp[u] = max(dp[u],sum+val[0]+val[1]) ;
}

int32_t main()
{
	ios::sync_with_stdio(0) ; cin.tie(0) ; 
	int n ; 
	cin >> n ; 
	for(int i = 1 ; i < n ; i ++ ) 
	{
		int x , y , z ; 
		cin >> x >> y >> z ; 
		adj[x].pb({y,z}) ; 
		adj[y].pb({x,z}) ; 
	}
	int ans = 1e18 ;
	for(int i = 1 ; i <= n ; i ++ ) {
		dfs(i,0) ; 
		ans = min(ans,dp[i]) ; 
	}
	cout << ans << endl ; 
}

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