解法：显然的链剖。维护区间max,min，前面减后面的max,后面减前面的max即可
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> using namespace std; struct Tree{ int lr,rl,mx,mn,bz; }tr[400011]; Tree Tm[111]; int g[50011],next[100011],y[100011],num[50011],dep[50011],fa[50011],top[50011]; int id[50011],son[50011],size[50011],pm[111],sm[111],val[50011]; int tot,tt,n,i,x,z,q,ans,m; struct AA{ int l,r,k,sh; }que[111]; void star(int i,int j) { tt++; next[tt]=g[i]; g[i]=tt; y[tt]=j; } void build_chain(int root) { int x; x=root; while(x){ tot++; id[tot]=x; num[x]=tot; top[x]=root; x=son[x]; } } void dfs(int x) { int j,k; size[x]=1; j=g[x]; while(j!=0){ k=y[j]; if(k!=fa[x]){ fa[k]=x; dep[k]=dep[x]+1; dfs(k); size[x]+=size[k]; if(size[k]>size[son[x]]){ if(son[x])build_chain(son[x]); son[x]=k; } else build_chain(k); } j=next[j]; } } Tree Merge(Tree a,Tree b) { Tree c; c.mx=max(a.mx,b.mx); c.mn=min(a.mn,b.mn); c.rl=max(a.rl,b.rl); c.rl=max(c.rl,b.mx-a.mn); c.lr=max(a.lr,b.lr); c.lr=max(c.lr,a.mx-b.mn); return c; } void up(int t) { Tree a,b; Tree &c=tr[t]; a=tr[t+t];b=tr[t+t+1]; c.mx=max(a.mx,b.mx); c.mn=min(a.mn,b.mn); c.rl=max(a.rl,b.rl); c.rl=max(c.rl,b.mx-a.mn); c.lr=max(a.lr,b.lr); c.lr=max(c.lr,a.mx-b.mn); } void build(int l,int r,int t) { if(l==r){ tr[t].mx=tr[t].mn=val[id[l]]; tr[t].lr=tr[t].rl=0; tr[t].bz=0; return; } int mid; mid=(l+r)/2; build(l,mid,t+t); build(mid+1,r,t+t+1); tr[t].bz=0; up(t); } void change(int t,int x) { tr[t].bz+=x; tr[t].mx+=x; tr[t].mn+=x; } void down(int t,int l,int r) { if(l==r)return; if(tr[t].bz){ change(t+t,tr[t].bz); change(t+t+1,tr[t].bz); tr[t].bz=0; } } void insert(int t,int l,int r,int x,int y,int z) { down(t,l,r); if(l==x&&r==y){ change(t,z); return; } int mid; mid=(l+r)/2; if(y<=mid)insert(t+t,l,mid,x,y,z); if(x>mid)insert(t+t+1,mid+1,r,x,y,z); if(x<=mid&&y>mid){ insert(t+t,l,mid,x,mid,z); insert(t+t+1,mid+1,r,mid+1,y,z); } up(t); } Tree ask(int t,int l,int r,int x,int y) { down(t,l,r); if(l==x&&r==y)return tr[t]; Tree re; int mid; mid=(l+r)/2; if(y<=mid)re=ask(t+t,l,mid,x,y); if(x>mid)re=ask(t+t+1,mid+1,r,x,y); if(x<=mid&&y>mid)re=Merge(ask(t+t,l,mid,x,mid),ask(t+t+1,mid+1,r,mid+1,y)); up(t); return re; } bool cmp(AA a,AA b) { if(a.k==b.k){ if(a.k==1)return a.sh<b.sh; else return a.sh>b.sh; } else return a.k<b.k; } void Work(int st,int ed,int ad) { int bs,be,mn[3],i,ts(0); bs=1;be=2; mn[1]=mn[2]=0; while(true){ if(top[st]==top[ed]){ if(dep[st]<dep[ed])swap(st,ed),swap(bs,be); ts++; que[ts].l=num[ed]; que[ts].r=num[st]; que[ts].k=bs; que[ts].sh=++mn[bs]; break; } else{ if(dep[top[st]]<dep[top[ed]])swap(st,ed),swap(bs,be); ts++; que[ts].l=num[top[st]]; que[ts].r=num[st]; que[ts].k=bs; que[ts].sh=++mn[bs]; st=fa[top[st]]; } } sort(que+1,que+1+ts,cmp); for(i=1;i<=ts;i++)insert(1,1,n,que[i].l,que[i].r,ad); pm[0]=214748364; sm[ts+1]=-214748364; for(i=1;i<=ts;i++)Tm[i]=ask(1,1,n,que[i].l,que[i].r); for(i=1;i<=ts;i++)pm[i]=min(pm[i-1],Tm[i].mn); for(i=ts;i>=1;i--)sm[i]=max(sm[i+1],Tm[i].mx); ans=-214748364; for(i=1;i<=ts;i++){ if(que[i].k==2)ans=max(ans,Tm[i].rl); else ans=max(ans,Tm[i].lr); ans=max(ans,sm[i+1]-pm[i]); } } int main() { scanf("%d",&n); for(i=1;i<=n;i++)scanf("%d",&val[i]); for(i=1;i<n;i++){ scanf("%d%d",&x,&z); star(x,z); star(z,x); } scanf("%d",&m); dfs(1); build_chain(1); build(1,n,1); for(i=1;i<=m;i++){ scanf("%d%d%d",&x,&z,&q); Work(x,z,q); printf("%d ",ans); } }