【hdu 5052】

#include<cstdio> #include<cstring> #include<iostream> #define maxn 1000021 #define ls(u) ch[u][0] #define rs(u) ch[u][1] #define inf 0x3fffffff using namespace std; int T,n,m,ch[maxn][2],Max[maxn],Min[maxn],val[maxn],lz[maxn]; int q[maxn],fa[maxn],flag[maxn],ans[maxn],head[maxn],tot=1,ans2[maxn]; struct edge{int v,next;}e[maxn*2]; void adde(int a,int b){e[tot].v=b,e[tot].next=head[a];head[a]=tot++;} void pre(){ Max[0]=-inf,Min[0]=inf; for(int i=1;i<=n;i++){ ls(i)=rs(i)=0;fa[i]=0; head[i]=lz[i]=flag[i]=ans[i]=0; }fa[1]=0,tot=1; } inline int Q(int u){return u==rs(fa[u]);} inline int isrt(int u){return !fa[u]||(u!=ls(fa[u])&&u!=rs(fa[u]));} inline void push_up(int u){ Max[u]=max(max(Max[ls(u)],Max[rs(u)]),val[u]); Min[u]=min(min(Min[ls(u)],Min[rs(u)]),val[u]); ans[u]=max(ans[ls(u)],ans[rs(u)]); ans[u]=max(ans[u],Max[rs(u)]-Min[ls(u)]); ans[u]=max(ans[u],val[u]-Min[ls(u)]); ans[u]=max(ans[u],Max[rs(u)]-val[u]); ans2[u]=max(ans2[ls(u)],ans2[rs(u)]); ans2[u]=max(ans2[u],Max[ls(u)]-Min[rs(u)]); ans2[u]=max(ans2[u],val[u]-Min[rs(u)]); ans2[u]=max(ans2[u],Max[ls(u)]-val[u]); } inline void change(int u,int x){ val[u]+=x,lz[u]+=x; Max[u]+=x,Min[u]+=x; } inline void push_down(int u){ if(!flag[u]&&!lz[u])return; if(flag[u]){ swap(ls(u),rs(u)); if(ls(u))flag[ls(u)]^=1,swap(ans[ls(u)],ans2[ls(u)]); if(rs(u))flag[rs(u)]^=1,swap(ans[rs(u)],ans2[rs(u)]); flag[u]=0; } if(lz[u]){ if(ls(u))change(ls(u),lz[u]); if(rs(u))change(rs(u),lz[u]); lz[u]=0; } } void rotate(int u){ int d=!Q(u),f=fa[u],ff=fa[f]; if(!isrt(f))ch[ff][Q(f)]=u;fa[u]=ff; if(ch[u][d])fa[ch[u][d]]=f;ch[f][!d]=ch[u][d]; fa[f]=u,ch[u][d]=f; push_up(f);push_up(u); } void splay(int u){ int x=u; for(q[*q=1]=u;!isrt(x);x=fa[x])q[++(*q)]=fa[x]; for(int i=*q;i>=1;i--)push_down(q[i]); for(int i=1;i<=*q;i++)push_up(q[i]); while(!isrt(u)){ int f=fa[u]; if(isrt(f))rotate(u); else{ if(Q(f)==Q(u))rotate(f); else rotate(u); rotate(u); } } } void access(int u){ for(int x=0;u;u=fa[x=u]){ splay(u);rs(u)=x; push_up(u); } } void makert(int u){ access(u); splay(u);flag[u]^=1; swap(ans[u],ans2[u]); } void query(int a,int b,int v){ makert(a);access(b); splay(b);printf("%d\n",ans[b]); change(b,v); } void dfs(int u,int f){ fa[u]=f; for(int v,i=head[u];i;i=e[i].next){ if((v=e[i].v)==f)continue; dfs(v,u); } } void solve(){ scanf("%d",&m); int a,b,v; while(m--){ scanf("%d%d%d",&a,&b,&v); query(a,b,v); } } int main(){ scanf("%d",&T); while(T--){ scanf("%d",&n); pre(); for(int i=1;i<=n;i++)scanf("%d",val+i); for(int a,b,i=1;i<n;i++){ scanf("%d%d",&a,&b); adde(a,b),adde(b,a); }dfs(1,0); solve(); } return 0; }