제출 #752021

#제출 시각아이디문제언어결과실행 시간메모리
752021boyliguanhan구슬과 끈 (APIO14_beads)C++17
100 / 100
191 ms33104 KiB
#include<bits/stdc++.h>
#define N 200100
#define int long long
using namespace std;
int n,f[N], a3[N],dp[N][2],dp2[N][2], a1[N],a2[N], bst[N],I=1e18;
vector<pair<int, int>> adj[N];
void dfs(int x){
	dp[x][0]=0;
	int m1=I,m2=I+1;
	for(auto [i,j]:adj[x])
        if(f[x]!=i){
            a3[i]=j;
            f[i]=x,dfs(i);
            int m=max(dp[i][1]+j,dp[i][0]);
            dp[x][0]+=m,m-=(dp[i][0]+j);
            if(m<m1)
                m2=m1,m1=m,bst[x]=i;
            else if(m<m2)
                m2=m;
        }
	a1[x]=m1,a2[x]=m2,dp[x][1]=dp[x][0]-a1[x];
}
void dfs2(int x){
	for(auto [i, j]:adj[x])
        if(i!=f[x]){
            dp2[i][0]=dp[x][0]-max(dp[i][1]+j,dp[i][0]);
            if(x>1)dp2[i][0]+=max(dp2[x][1]+a3[x],dp2[x][0]);
            int M=((bst[x]==i)?a2[x]:a1[x]);
            if(x>1)M=min(M,max(dp2[x][1]+a3[x],dp2[x][0])-(dp2[x][0]+a3[x]));
            dp2[i][1]=dp2[i][0]-M;
            dfs2(i);
        }
}
signed main(){
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
	cin >> n;
	for(int i=1;i<n;i++){
        int a, b, c;
		cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
	}
	dfs(1);
	dfs2(1);
	int ans=-I;
	for(int i=1;i<=n;i++){
		int temp=dp[i][0];
		if(i > 1)
            temp+=max(dp2[i][0],dp2[i][1]+a3[i]);
		ans=max(ans,temp);
	}
	cout << ans << '\n';
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...