제출 #1194154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194154		boclobanchat	구슬과 끈 (APIO14_beads)	C++20	100 / 100	83 ms	27060 KiB

beads

#include<bits/stdc++.h>
using namespace std;
#define ii pair<long long,long long>
#define fi first
#define se second
const int MAXN=2e5+5;
const long long INF=1e18;
long long dp[MAXN][2],ans[MAXN],F[MAXN][2];
vector<ii> ds[MAXN];
void dfs(int i,int pre)
{
	long long mx=-INF,sum=0;
	for(auto v:ds[i]) if(v.fi!=pre)
	{
		dfs(v.fi,i);
		mx=max(mx,-max(dp[v.fi][0],dp[v.fi][1]+v.se)+dp[v.fi][0]+v.se);
		sum+=max(dp[v.fi][0],dp[v.fi][1]+v.se);
	}
	dp[i][1]=sum+mx,dp[i][0]=sum;
}
void dfsus(int i,int pre,int d)
{
	ii mx={-INF,-INF};
	long long sum=0;
	if(i!=pre)
	{
		sum+=max(F[i][0],F[i][1]+d);
		long long k=-max(F[i][0],F[i][1]+d)+F[i][0]+d;
		if(mx.fi<k) mx.se=mx.fi,mx.fi=k;
		else if(mx.se<k) mx.se=k;
	}
	for(auto v:ds[i]) if(v.fi!=pre) 
	{
		sum+=max(dp[v.fi][0],dp[v.fi][1]+v.se);
		long long k=-max(dp[v.fi][0],dp[v.fi][1]+v.se)+dp[v.fi][0]+v.se;
		if(mx.fi<k) mx.se=mx.fi,mx.fi=k;
		else if(mx.se<k) mx.se=k;
	}
	ans[i]=sum;
	for(auto v:ds[i]) if(v.fi!=pre)
	{
		long long k=-max(dp[v.fi][0],dp[v.fi][1]+v.se)+dp[v.fi][0]+v.se;
		if(mx.fi==k) F[v.fi][1]=sum-max(dp[v.fi][0],dp[v.fi][1]+v.se)+mx.se;
		else F[v.fi][1]=sum-max(dp[v.fi][0],dp[v.fi][1]+v.se)+mx.fi;
		F[v.fi][0]=sum-max(dp[v.fi][0],dp[v.fi][1]+v.se);
		dfsus(v.fi,i,v.se);
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int l,r,v;
		cin>>l>>r>>v;
		ds[l].push_back({r,v}),ds[r].push_back({l,v});
	}
	dfs(1,1);
	dfsus(1,1,0);
	long long a=0;
	for(int i=1;i<=n;i++) a=max(a,ans[i]);
	cout<<a;
}

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