非常难想的树形DP。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int N=100010; 6 int cnt,fir[N],nxt[N*2],to[N*2],val[N*2]; 7 int n,w[N],ans[N],fa[N],f1[N][2],f2[N][2]; 8 void addedge(int a,int b,int v){ 9     nxt[++cnt]=fir[a];to[fir[a]=cnt]=b;val[cnt]=v;10     nxt[++cnt]=fir[b];to[fir[b]=cnt]=a;val[cnt]=v;11 }12 13 void DFS(int x){
   int ret=0;14     f1[x][0]=f1[x][1]=w[x];15     for(int i=fir[x];i;i=nxt[i])16         if(to[i]!=fa[x]){17             fa[to[i]]=x;DFS(to[i]);18             f1[to[i]][0]=max(f1[to[i]][0]-val[i],0);19             f1[to[i]][1]=max(f1[to[i]][1]-val[i]*2,0);20             ret=max(ret,f1[to[i]][0]-f1[to[i]][1]);21             f1[x][1]+=f1[to[i]][1];22         }23     f1[x][0]=f1[x][1]+ret;    24 }25 26 void DP(int x){27     int ret=w[x],v1=0,v2=0,p=0;28     if(fa[x]){29         ret+=f2[x][1];30         int tmp=f2[x][0]-f2[x][1];31         if(tmp>v1)v2=v1,v1=tmp;32         else if(tmp>v2)v2=tmp;33     }34     for(int i=fir[x];i;i=nxt[i])35         if(to[i]!=fa[x]){36             ret+=f1[to[i]][1];37             int tmp=f1[to[i]][0]-f1[to[i]][1];38             if(tmp>v1)v2=v1,v1=tmp,p=to[i];39             else if(tmp>v2)v2=tmp;40         }41     ans[x]=ret+v1;42     for(int i=fir[x];i;i=nxt[i])43         if(to[i]!=fa[x]){44             f2[to[i]][1]=ret-f1[to[i]][1]-val[i]*2;45             if(to[i]!=p)f2[to[i]][0]=f2[to[i]][1]+v1+val[i];46             else f2[to[i]][0]=f2[to[i]][1]+v2+val[i];47             f2[to[i]][0]=max(f2[to[i]][0],0);48             f2[to[i]][1]=max(f2[to[i]][1],0);49             DP(to[i]);50         }51 }52 53 void Init(){54     memset(fir,0,sizeof(fir));55     memset(f1,0,sizeof(f1));56     memset(f2,0,sizeof(f2));57     memset(fa,0,sizeof(fa));58     cnt=0;59 }60 61 int T,cas;62 int main(){63     scanf("%d",&T);64     while(T--){65         Init();66         scanf("%d",&n);67         for(int i=1;i<=n;i++)scanf("%d",&w[i]);68         for(int i=1,a,b,v;i