제출 #713087

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713087		bin9638	구슬과 끈 (APIO14_beads)	C++17	0 / 100	5 ms	8148 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 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]
    int f[4];
    f[0]=f[1]=f[2]=f[3]=-1e12;
    for(auto v:g[u])
        if(v.sc!=p)
        {
            dp[u][0]+=max(dp[v.sc][0],dp[v.sc][1]+v.fs);
            f[3]=dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs);
            sort(f,f+4,greater<int>());
            //cout<<u<<" "<<v.sc<<" "<<dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs)<<endl;
        }
    int dm=dp[u][0];
    selfmax(dp[u][0],dp[u][0]+f[0]+f[1]);
    //dp[v.sc][1]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs)
    //dp[u][1]
    for(auto v:g[u])
        if(v.sc!=p)
        {
            int sum=dm-max(dp[v.sc][0],dp[v.sc][1]+v.fs);
            if(dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs)!=f[0])
                selfmax(dp[u][1],dp[v.sc][0]+v.fs+sum+max(0ll,f[0]+f[1]));
                    else  selfmax(dp[u][1],dp[v.sc][0]+v.fs+sum+max(0ll,f[2]+f[1]));
        }
    //cout<<u<<" "<<dp[u][0]<<" "<<dp[u][1]<<endl;
}

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][0];
    return 0;
}

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