제출 #197728

#제출 시각아이디문제언어결과실행 시간메모리
197728moonrabbit2구슬과 끈 (APIO14_beads)C++17
100 / 100
250 ms26328 KiB
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef vector<vector<ll>> mat;
const ll mod=1e9+7;
const int N=2e5+5;
int n,ans,dp1[N],dp2[N],dp3[N],dp4[N],val[N];
vector<pii> g[N];
//dp1 : 없/끝, dp2 : 없/부모로, dp3 : 있/끝, dp4 : 있/부모로
void dfs(int x,int p){
    vector<int> v;
    dp2[x]=dp3[x]=dp4[x]=-1e9;
    int s=0;
    for(auto &it : g[x]) if(it.fi!=p){
        int u=it.fi,c=it.se;
        dfs(u,x);
        val[u]=max(dp1[u],dp2[u]+c);
        dp1[x]+=max(dp1[u],dp2[u]+c);
        v.emplace_back(dp1[u]-val[u]+c);
        s+=val[u];
    }
    sort(v.begin(),v.end()); reverse(v.begin(),v.end());
    for(auto &it : g[x]) if(it.fi!=p){
        int u=it.fi,c=it.se;
        dp2[x]=max(dp2[x],dp1[x]-val[u]+dp1[u]+c);
        dp3[x]=max(dp3[x],dp1[x]-val[u]+max(dp3[u],dp4[u]+c));
        dp4[x]=max(dp4[x],dp1[x]-val[u]+dp3[u]+c);
    }
    if(v.size()>=2){
        for(auto &it : g[x]) if(it.fi!=p){
            int u=it.fi,c=it.se;
            if(dp1[u]-val[u]+c==v[0]) dp3[x]=max(dp3[x],dp1[x]-val[u]+max(dp1[u],dp3[u])+c+v[1]);
            else dp3[x]=max(dp3[x],dp1[x]-val[u]+max(dp1[u],dp3[u])+c+v[0]);
        }
    }
    //cout<<x<<" : "<<dp1[x]<<" "<<dp2[x]<<" "<<dp3[x]<<" "<<dp4[x]<<"\n";
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
	cin>>n; int s=0;
    for(int u,v,c,i=1;i<n;i++){
        cin>>u>>v>>c;
        s+=c;
        g[u].emplace_back(v,c);
        g[v].emplace_back(u,c);
    }
    dfs(1,0);
    cout<<max(dp1[1],dp3[1]);
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...