[bzoj3677][Apio2014]连珠线【树形dp】

【题目链接】
　　https://www.lydsy.com/JudgeOnline/problem.php?id=3677
【题解】
　　首先一定存在一个点，当他作为根时所有个蓝线都以x-dad[x]-dad[dad[x]]存在。因此可以先确定一个根，O(N)$O(N)$dp一下，然后O(1)$O(1)$换根。
　　时间复杂度:O(N)$O(N)$
　　

/* --------------
    user Vanisher
    problem bzoj-3677 
----------------*/
# include <bits/stdc++.h>
# define    ll      long long
# define    inf     0x3f3f3f3f
# define    N       200010
using namespace std;
int read(){
    int tmp=0, fh=1; char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') fh=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){tmp=tmp*10+ch-'0'; ch=getchar();}
    return tmp*fh;
}
struct edge{
    int data,next,vote;
}e[N*2];
int place,f[N][3],g[N][3],head[N],st[N*2],top,rd[N*2],n,ans,use[N];
void build(int u, int v, int w){
    e[++place].data=v; e[place].next=head[u]; head[u]=place; e[place].vote=w;
    e[++place].data=u; e[place].next=head[v]; head[v]=place; e[place].vote=w;
}
void dp(int x, int fa){
    f[x][0]=0; f[x][1]=-inf; f[x][2]=-inf; 
    for (int ed=head[x]; ed!=0; ed=e[ed].next)
        if (e[ed].data!=fa){
            dp(e[ed].data,x);
            int now=max(f[e[ed].data][1]+e[ed].vote,f[e[ed].data][0]);
            f[x][1]+=now, f[x][2]+=now;
            if (f[x][0]+f[e[ed].data][0]+e[ed].vote>f[x][1]){
                g[x][2]=g[x][1], f[x][2]=f[x][1];
                f[x][1]=f[x][0]+f[e[ed].data][0]+e[ed].vote;
                g[x][1]=e[ed].data;
            }
            else if (f[x][0]+f[e[ed].data][0]+e[ed].vote>f[x][2]){
                f[x][2]=f[x][0]+f[e[ed].data][0]+e[ed].vote;
                g[x][2]=e[ed].data;
            }
            f[x][0]=f[x][0]+now;
        }   
}
void dfs(int x, int fa){
    st[++top]=x;
    for (int ed=head[x]; ed!=0; ed=e[ed].next)
        if (e[ed].data!=fa){
            rd[top]=e[ed].vote;
            dfs(e[ed].data,x);
            rd[top]=e[ed].vote;
            st[++top]=x;
        }
}
int main(){
    n=read();
    for (int i=1; i<n; i++){
        int u=read(), v=read(), w=read();
        build(u,v,w);
    }
    dp(1,0);
    dfs(1,0);
    ans=f[1][0]; use[1]=true;
    for (int i=1; i<top; i++){
        int x=st[i], y=st[i+1], tag;
        if (g[y][1]==x) tag=2; else tag=1;
        f[x][0]=f[x][0]-max(f[y][tag]+rd[i],f[y][0]);
        f[x][1]=f[x][1]-max(f[y][tag]+rd[i],f[y][0]);
        f[x][2]=f[x][2]-max(f[y][tag]+rd[i],f[y][0]);
        if (g[x][1]==y) tag=2; else tag=1;
        if (use[y]==0){
            f[y][1]=f[y][1]+max(f[x][tag]+rd[i],f[x][0]);
            f[y][2]=f[y][2]+max(f[x][tag]+rd[i],f[x][0]);
            if (f[y][0]+f[x][0]+rd[i]>f[y][1]){
                g[y][2]=g[y][1], f[y][2]=f[y][1];
                f[y][1]=f[y][0]+f[x][0]+rd[i];
                g[y][1]=x;
            }
            else if (f[y][0]+f[x][0]+rd[i]>f[y][2]){
                f[y][2]=f[y][0]+f[x][0]+rd[i];
                g[y][2]=x;
            }
            use[y]=true;
        }
        else {
            f[y][1]=f[y][1]+max(f[x][tag]+rd[i],f[x][0]);
            f[y][2]=f[y][2]+max(f[x][tag]+rd[i],f[x][0]);
        }
        f[y][0]=f[y][0]+max(f[x][tag]+rd[i],f[x][0]);
        ans=max(ans,f[y][0]);
    }
    printf("%d
",ans);
    return 0;
}