义乌中学暑假集训 2021.07.15 C

#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
#define LL long long
using namespace std;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(LL x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x%10+'0');}
Cn int N=1e5+10;
int n,a[N],fir[N],nxt[N<<1],son[N<<1],tot;
LL Mx,Ans,f[N],g[N],Mx1,Mx2;
I void Add(CI x,CI y){nxt[++tot]=fir[x],fir[x]=tot,son[tot]=y;}
#define to son[i]
I void Dfs(CI x,CI fa){
    RI i,sz=0,Mx1=0,Mx2=0,id1=0,id2=0;for(i=fir[x];i;i=nxt[i]) if(to^fa) sz++,Dfs(to,x),g[x]=max(g[x],g[to]),f[to]>Mx1?(Mx2=Mx1,id2=id1,Mx1=f[to],id1=to):f[to]>Mx2&&(Mx2=f[to],id2=to);
    if(!Mx1&&!Mx2) return Ans=max(Ans,f[x]=g[x]=a[x]),void();
    f[x]=a[x]+f[id1],g[x]=max(g[x],f[x]);
    if(!Mx2) return Ans=max(Ans,f[x]),void();
    g[x]=max(g[x],f[x]+f[id2]);
    if(sz==2) return Ans=max(Ans,max(f[x]+g[id2],g[id1]+a[x]+f[id2])),void();
    for(i=fir[x];i;i=nxt[i]) to^fa&&to^id1&&to^id2&&(Ans=max(Ans,max(f[x]+f[id2]+g[to],max(a[x]+f[to]+f[id2]+g[id1],a[x]+f[to]+f[id1]+g[id2]))));
}
I void Dfs2(CI x,CI fa,LL S){
    RI i,Mx1=0,Mx2=0,id1=0,id2=0;for(i=fir[x];i;i=nxt[i]) if(to^fa) f[to]>Mx1?(Mx2=Mx1,id2=id1,Mx1=f[to],id1=to):f[to]>Mx2&&(Mx2=f[to],id2=to);
    for(i=fir[x];i;i=nxt[i]) if(to^fa) to^id1?(Ans=max(Ans,S+f[id1]+g[to]),Dfs2(to,x,max(S,f[x])+a[to]),0):(Ans=max(Ans,S+f[id2]+g[to]),Dfs2(to,x,max(S,f[id2]+a[x])+a[to]),0); 
}
int main(){
    RI i,j,x,y;for(read(n),i=1;i<=n;i++) read(a[i]);
    for(i=1;i<n;i++) read(x),read(y),Add(x,y),Add(y,x);
    return Dfs(1,0),Dfs2(1,0,a[1]),write(Ans),0;
}