[TJOI2015]旅遊 [樹鍊剖分神題]

​​傳送門​​

第一眼看是樹剖加鍊上最大最小 , 但必須保證最小出現在最大之前

于是我們考慮直接維護一個區間最大最小的差 (保證最小在最大之前)

我們發現,這個差就是 

等等,我們從下往上走和從上往下方向不同(廢話)

也就是說我們從下往上要用的是上面的最大-下面的最小

反之則是下面的最大-上面的最小

于是我們考慮維護兩個(lval,rval)

然後考慮樹剖時如何合并??

我們将最大最小存在數組裡 , 然後O(個數^2)掃一遍更新ans

因為重鍊+輕鍊的個數<log(n) , 是以總複雜度為O(nlogn^2)

為了友善 , 我們先處理x到lca的 , 再處理lca到y的

我們還需要記錄x到lca的最小, 與lca到y的最大,然後再打一下擂台

//寫過的最長代碼 (170)
#include<bits/stdc++.h>
#define N 50050
#define M N*2
#define LL long long
#define inf 0x3fffffff
using namespace std;
int first[N],next[M],to[M],tot;
int fa[N],son[N],id[N],dep[N];
int sign,top[N],siz[N],pre[N];
int n,a[N],m; LL ans,Max[25],Min[25],tmp;
struct Node{
  int l,r; 
  LL tag,Min,Max;
  LL lval,rval; 
}t[N<<2];
void add(int x,int y){
  next[++tot]=first[x],first[x]=tot,to[tot]=y;
}
void dfs1(int u,int f){
  siz[u]=1;
  for(int i=first[u];i;i=next[i]){
    int t=to[i]; if(t==f) continue;
    fa[t]=u,dep[t]=dep[u]+1; dfs1(t,u); siz[u]+=siz[t];
    if(siz[t]>siz[son[u]]) son[u]=t; 
  }
}
void dfs2(int u,int Top){
  id[u]=++sign,top[u]=Top,pre[sign]=u;
  if(son[u]) dfs2(son[u],Top);
  for(int i=first[u];i;i=next[i])
    if(to[i]!=fa[u] && to[i]!=son[u]) dfs2(to[i],to[i]);
}
/*----------------------------------------線段樹-------------------------------------*/
void Pushup(int x){
  t[x].Max = max(t[x<<1].Max , t[x<<1|1].Max);
  t[x].Min = min(t[x<<1].Min , t[x<<1|1].Min);
  t[x].lval = max( max(t[x<<1].lval , t[x<<1|1].lval) , t[x<<1|1].Max - t[x<<1].Min);
  t[x].rval = max( max(t[x<<1].rval , t[x<<1|1].rval) , t[x<<1].Max - t[x<<1|1].Min);
}
void Pushdown(int x){
  if(t[x].tag){
    t[x<<1].Min += t[x].tag;
    t[x<<1|1].Min += t[x].tag;
    t[x<<1].Max += t[x].tag;
    t[x<<1|1].Max += t[x].tag;
    t[x<<1].tag += t[x].tag;
    t[x<<1|1].tag += t[x].tag;
    t[x].tag = 0;  
  }
}
void build(int x,int l,int r){
  t[x].l=l,t[x].r=r;
  if(l==r){t[x].Min=t[x].Max=a[pre[l]]; return;}
  int mid=(l+r)>>1;
  build(x<<1,l,mid),build(x<<1|1,mid+1,r);
  Pushup(x);
}
void quary(int x,int L,int R,Node &k){
  if(L<=t[x].l && t[x].r<=R){
    k.lval = max(k.lval,t[x].lval);
    k.rval = max(k.rval,t[x].rval);
    k.Max = max(k.Max,t[x].Max);
    k.Min = min(k.Min,t[x].Min);
    return;
  }
  Pushdown(x);
  int mid=(t[x].l+t[x].r)>>1;
  if(L>mid) quary(x<<1|1,L,R,k);
  else if(R<=mid) quary(x<<1,L,R,k);
  else{
    Node a,b; 
    a.Min=inf , a.Max=a.lval=a.rval=0;
    b.Min=inf , b.Max=b.lval=b.rval=0;
    quary(x<<1,L,R,a);
    quary(x<<1|1,L,R,b);
    k.lval = max(a.lval,b.lval);
    k.rval = max(a.rval,b.rval);
    k.lval = max(k.lval , b.Max-a.Min);
    k.rval = max(k.rval , a.Max-b.Min);
    k.Max = max(a.Max,b.Max);
    k.Min = min(a.Min,b.Min);
  }
}
void update(int x,int L,int R,int val){
  if(L<=t[x].l && t[x].r<=R){
    t[x].tag += val;  
    t[x].Min += val , t[x].Max += val;
    return;
  }
  Pushdown(x);
  int mid=(t[x].l+t[x].r)>>1;
  if(L<=mid) update(x<<1,L,R,val);
  if(R>mid) update(x<<1|1,L,R,val);
  Pushup(x);
}
/*-------------------------------------樹剖--------------------------------*/
int lca(int x,int y){
  while(top[x]!=top[y]){
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    x=fa[top[x]];
  }
  if(dep[x]<=dep[y]) swap(x,y);
  return y; 
}
void Q1(int x,int goal){
  int c1=0; Node now; tmp=inf;
  now.Min=inf , now.Max=now.lval=now.rval=0;
  while(top[x]!=top[goal]){
    now.Min=inf , now.Max=now.lval=now.rval=0;
    quary(1,id[top[x]],id[x],now); 
    ans = max(ans , now.rval);
    Max[++c1] = now.Max;
    Min[c1] = now.Min;
    x=fa[top[x]];
  }
  now.Min=inf , now.Max=now.lval=now.rval=0;
  quary(1,id[goal],id[x],now);
  ans = max(ans , now.rval);
  Max[++c1] = now.Max;
  Min[c1] = now.Min;
  for(int i=1;i<c1;i++) for(int j=i+1;j<=c1;j++) ans = max(ans , Max[j]-Min[i]);
  for(int i=1;i<=c1;i++) tmp = min(tmp,Min[i]); 
}
void Q2(int x,int goal){
  int c1=0;  Node now; 
  now.Min=inf , now.Max=now.lval=now.rval=0;
  while(top[x]!=top[goal]){
    now.Min=inf , now.Max=now.lval=now.rval=0;
    quary(1,id[top[x]],id[x],now); 
    ans = max(ans , now.lval);
    Max[++c1] = now.Max;
    Min[c1] = now.Min;
    x=fa[top[x]];
  }
  now.Min=inf , now.Max=now.lval=now.rval=0;
  quary(1,id[goal],id[x],now); 
  ans = max(ans , now.lval);
  Max[++c1] = now.Max;
  Min[c1] = now.Min;
  for(int i=1;i<c1;i++) for(int j=i+1;j<=c1;j++) ans = max(ans , Max[i]-Min[j]);
  for(int i=1;i<=c1;i++) ans = max(ans,Max[i]-tmp);
}
void Update(int x,int y,int val){
  while(top[x]!=top[y]){
    if(dep[top[x]]<dep[top[y]]) swap(x,y);
    update(1,id[top[x]],id[x],val);
    x=fa[top[x]];
  }
  if(dep[x]<dep[y]) swap(x,y);
  update(1,id[y],id[x],val);
}
int main(){
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  for(int i=1;i<=n-1;i++){
    int x,y; scanf("%d%d",&x,&y);
    add(x,y),add(y,x);
  }
  dep[1]=1,dfs1(1,0),dfs2(1,1),build(1,1,n);
  scanf("%d",&m); while(m--){
    Node now;now.Min=inf , now.Max=now.lval=now.rval=0;
    int x,y,val; scanf("%d%d%d",&x,&y,&val);
    int Lca=lca(x,y); ans = 0;
    Q1(x,Lca);
    Q2(y,Lca); printf("%lld\n",ans);
    Update(x,y,val); now.Min=inf , now.Max=now.lval=now.rval=0;
  }return 0; 
}