[APIO2014]连珠线

DP

题面

戳我

解析

放两考假时再补。。。做得我心累

#include<bits/stdc++.h>
using namespace std;
const int N=200005,inf=2000000005;
struct Edge{int to,nex,z;}e[N<<1];
struct data{int k,v;}d[N][2];
int n,num=0,ans=0,lis[N],f[N];
int I(){
    int x=0,f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';x=(x<<3)+(x<<1)+ch-'0',ch=getchar());
    return x*f;
}
void add(int x,int y,int z){
    e[++num].to=y;e[num].z=z;
    e[num].nex=lis[x];lis[x]=num;
}
void update(int x,int y,int v){
    if(v>=d[x][0].v)d[x][1]=d[x][0],d[x][0]=(data){y,v};
    else if(v>d[x][1].v)d[x][1]=(data){y,v};
}
void dp(int x,int fa){
    d[x][0].v=d[x][1].v=-inf;
    f[x]=0;
    for(int i=lis[x],y;i;i=e[i].nex)
        if((y=e[i].to)!=fa){
            dp(y,x);
            int t=max(f[y],f[y]+d[y][0].v+e[i].z);
            f[x]+=t;update(x,y,f[y]+e[i].z-t);
        }
}
void dfs(int x,int fa){
    ans=max(ans,f[x]);
    for(int i=lis[x],y;i;i=e[i].nex)
        if((y=e[i].to)!=fa){
            data d0=d[y][0],d1=d[y][1];
            int t1=f[y],t2=max(f[y],f[y]+d[y][0].v+e[i].z);
            int f1=f[x]-t2,f2=(d[x][0].k==y);
            int f3=max(f1,f[x]+d[x][f2].v-t2+e[i].z);
            f[y]+=f3;update(y,x,f1+e[i].z-f3);
            dfs(y,x);
            f[y]=t1;d[y][0]=d0;d[y][1]=d1;
        }
}
int main(){
    n=I();
    for(int i=1;i<n;++i){
        int x=I(),y=I(),z=I();
        add(x,y,z);add(y,x,z);
    }
    ans=-inf;dp(1,0);dfs(1,0);
    printf("%d\n",ans);
    return 0;
}