Submission #162253

#	Time	Username	Problem	Language	Result	Execution time	Memory
162253		HungAnhGoldIBO2020	Beads and wires (APIO14_beads)	C++14	0 / 100	6 ms	5112 KiB

beads

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+2;
const int inf=1e9+7;
vector<pair<int,int> > adj[N];
int dp[N][2][2][2];
void dfs(int x,int p,int val){
	int max1=-inf,max2=-inf,max3=-inf;
	for(auto j:adj[x]){
		int i=j.first;
		if(i!=p){
			dfs(i,x,j.second);
			dp[x][0][0][0]+=max(dp[i][0][0][0],dp[i][1][1][0]);
			if(max1<max(max(dp[i][0][0][0],dp[i][1][1][0]),max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][0][0][0],dp[i][1][1][0])){
				max1=max(max(dp[i][0][0][0],dp[i][1][1][0]),max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][0][0][0],dp[i][1][1][0]);
			}
			//for 0,0,1
			if(max2<=max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second){
				max3=max2;
				max2=max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second;
			}
			else{
				if(max3<max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second){
					max3=max(dp[i][0][0][0],max(dp[i][0][0][1],dp[i][1][0][1]))-max(dp[i][1][1][0],dp[i][0][0][0])+j.second;
				}
			}
			//for both 1,0,1 and 1,1,0
		}
	}
	dp[x][0][0][1]=dp[x][0][0][0]+max1;
	dp[x][1][1][0]=dp[x][0][0][0]+max2+val;
	dp[x][1][0][1]=dp[x][0][0][0]+max2+max3;
//	cout<<x<<' '<<dp[x][0][0][0]<<' '<<dp[x][0][0][1]<<' '<<dp[x][1][1][0]<<' '<<dp[x][1][0][1]<<'\n';
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l;
	cin>>n;
	for(i=1;i<n;i++){
		cin>>j>>k>>l;
		adj[j].push_back({k,l});
		adj[k].push_back({j,l});
	}
	dfs(1,1,-inf);
	cout<<max(dp[1][1][0][1],max(dp[1][0][0][0],dp[1][0][0][1]));
}
/*
5
1 2 10
1 3 40
1 4 15
1 5 20
60
*/
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
140
*/
/*
6
1 2 1
1 3 2
3 4 1
1 5 2
5 6 3 
8
*/

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