Submission #713240

#	Time	Username	Problem	Language	Result	Execution time	Memory
713240		bin9638	Beads and wires (APIO14_beads)	C++17	100 / 100	240 ms	33984 KiB

beads

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 200010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double
#define int ll

int ans,dp[N][2],n;
vector<ii>g[N];

void selfmax(int&u,int v)
{
    u=max(u,v);
}

void DFS(int u,int p)
{
    dp[u][0]=0;
    for(auto v:g[u])
        if(v.sc!=p)
            DFS(v.sc,u);
    //dp[u][0]
    for(auto v:g[u])
        if(v.sc!=p)
        {
            dp[u][0]+=max(dp[v.sc][0],dp[v.sc][1]+v.fs);
        }
    int dm=dp[u][0];
    for(auto v:g[u])
        if(v.sc!=p)
        {
            int sum=dm-max(dp[v.sc][0],dp[v.sc][1]+v.fs);
            selfmax(dp[u][1],dp[v.sc][0]+v.fs+sum);
        }
   // cout<<u<<" "<<dp[u][0]<<" "<<dp[u][1]<<endl;
}

void solve(int u,int p,vector<int>cha,int L)
{
   //  cout<<u<<" "<<cha[0]<<" "<<cha[1]<<endl;
    int f[3];
    f[0]=f[1]=f[2]=-1e12;
    int val=(p!=0 ? max(cha[0],cha[1]+L) : 0 );
    if(p!=0)
        f[0]=cha[0]+L-max(cha[0],cha[1]+L);
    //cout<<u<<" "<<val<<" "<<cha[0]<<" "<<cha[1]<<endl;
    for(auto v:g[u])
        if(v.sc!=p)
        {
            val+=max(dp[v.sc][0],dp[v.sc][1]+v.fs);
             f[2]=dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs);
            sort(f,f+3,greater<int>());
        }
    if(f[0]+f[1]>0)
        val+=f[0]+f[1];
    ans=max(ans,val);
    int sum=(p!=0 ? max(cha[0],cha[1]+L) : 0);
    for(auto v:g[u])
        if(v.sc!=p)
        {
            sum+=max(dp[v.sc][0],dp[v.sc][1]+v.fs);
        }
    //cout<<sum<<endl;
  //  f[0]=f[1]=f[2]=-1e12;
   // if(p!=0)
     //   f[0]=cha[0]+L-max(cha[0],cha[1]+L);
    for(auto v:g[u])
        if(v.sc!=p)
        {
                vector<int>s={sum-max(dp[v.sc][0],dp[v.sc][1]+v.fs),sum-max(dp[v.sc][0],dp[v.sc][1]+v.fs),sum-max(dp[v.sc][0],dp[v.sc][1]+v.fs)+
                  (dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs)==f[0] ? f[1] : f[0])};
            s[1]=sum-max(dp[v.sc][0],dp[v.sc][1]+v.fs)+
                  (dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs)==f[0] ? f[1] : f[0]);
         //   if(u==1&&v.sc==3)
            {
              //  cout<<"cc "<<u<<" "<<v.sc<<" "<<s[1]<<" "<<sum-max(dp[v.sc][0],dp[v.sc][1]+v.fs)+
                 // (dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs)==f[0] ? f[1] : f[0])<<endl;
            }
            solve(v.sc,u,s,v.fs);
        }
}

int32_t main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(dp,-0x3f3f,sizeof(dp));
    cin>>n;
    int sum=0;
    for(int i=1;i<n;i++)
    {
        int u,v,L;
        cin>>u>>v>>L;
        g[u].pb({L,v});
        g[v].pb({L,u});
        sum+=L;
    }
    //cout<<sum<<endl;
    DFS(1,0);
   // cout<<dp[1][1]<<endl;
    solve(1,0,{(int)-1e12,(int)-1e12},0);
    cout<<ans;
    return 0;
}

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