90pts 这孩子还有希望吗/kk
查看原帖
90pts 这孩子还有希望吗/kk
38171
DeNeRATe楼主2020/9/23 20:26
//P3647
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define INF 0x3f3f3f3f3f3f3f3f
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const LL MaxN=2e5+10;

LL Next[MaxN<<1],End[MaxN<<1],Head[MaxN],Cur,Val[MaxN<<1];
LL Total,u,v,w,Ans=0;
LL DP[MaxN][2],Sec[MaxN];
LL Son[MaxN];

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Add_Edge(LL From,LL To,LL Temp) {
    Next[++Cur]=Head[From];
    Head[From]=Cur;
    End[Cur]=To;
    Val[Cur]=Temp;
}

inline void DFS_one(LL New,LL Pre) {
    for(LL i=Head[New];i;i=Next[i]) {
        if(End[i]==Pre) continue;
        DFS_one(End[i],New);
        DP[New][0]+=max(DP[End[i]][0],DP[End[i]][1]+Val[i]);
    }
    DP[New][1]=-INF; Sec[New]=-INF;
    for(LL i=Head[New];i;i=Next[i]) {
        if(End[i]==Pre) continue;
        LL Max=max(DP[End[i]][0],DP[End[i]][1]+Val[i]);
        if(DP[New][0]-Max+DP[End[i]][0]+Val[i]>DP[New][1]) {
            Sec[New]=DP[New][1];
            DP[New][1]=DP[New][0]-Max+DP[End[i]][0]+Val[i];
            Son[New]=End[i];
        } else if(DP[New][0]-Max+DP[End[i]][0]+Val[i]>Sec[New]) 
            Sec[New]=DP[New][0]-Max+DP[End[i]][0]+Val[i];
    }
}

inline void DFS_two(LL New,LL Pre) {
    Ans=max(Ans,DP[New][0]);
    for(LL i=Head[New];i;i=Next[i]) {
        if(End[i]==Pre) continue;
        LL Max_one=max(DP[End[i]][1]+Val[i],DP[End[i]][0]);
        LL Max_two=DP[New][0]-Max_one;
        if(Son[New]==End[i]) { Max_two=max(Max_two,Sec[New]-Max_one+Val[i]); }
        else { Max_two=max(Max_two,DP[New][1]-Max_one+Val[i]); }
        DP[End[i]][0]+=Max_two;
        DP[End[i]][1]+=Max_two;
        Sec[End[i]]+=Max_two;
        if(DP[End[i]][0]-Max_two+DP[New][0]-Max_one+Val[i]>DP[End[i]][1]) {
            Sec[End[i]]=DP[End[i]][1];
            DP[End[i]][1]=DP[End[i]][0]-Max_two+DP[New][0]-Max_one+Val[i];
            Son[End[i]]=New;
        } else if(DP[End[i]][0]-Max_two+DP[New][0]-Max_one+Val[i]>Sec[End[i]]) 
            Sec[New]=DP[End[i]][0]-Max_two+DP[New][0]-Max_one+Val[i];
        DFS_two(End[i],New);
    }
}

signed main() {
    // File();
    ios::sync_with_stdio(false);
    cin>>Total;
    FOR(i,1,Total-1) { cin>>u>>v>>w; Add_Edge(u,v,w); Add_Edge(v,u,w); }
    DFS_one(1,0);
    DFS_two(1,0);
    cout<<Ans<<endl;
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}
2020/9/23 20:26
加载中...