ltor:从区间的左侧到右侧的最大利润

rtol：从区间的右侧到左侧的最大利润

mx：区间最大值

mn：区间最小值

#include<bits/stdc++.h>
using namespace std;

namespace IO
{
    const int I=1e6; char buf[I],stk[I],*p1,*p2;
    #define gc() (p1==p2&&(p2=(p1=buf)+cin.rdbuf()->sgetn(buf,I),p1==p2)?EOF:*p1++)
    template<typename T> inline void read(T &x)
    {
        x=0; int f=1; char ch;
        while(!isdigit(ch=gc())) if(ch=='-') f=-1;
        while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=gc();x*=f;
    }
    template<typename T,typename ...Args> inline void read(T &x, Args &...args) {read(x),read(args...);}
    template<typename T> inline void write(T x)
    {
        int top=0; if(x<0) cout.rdbuf()->sputc('-'),x=-x;
        if(!x) return cout.rdbuf()->sputc('0'),void();
        while(x) stk[++top]=x%10+48,x/=10;
        while(top) cout.rdbuf()->sputc(stk[top--]);
    }
    inline void write(const char *x) {while(*x){cout.rdbuf()->sputc(*(x++));}}
    template<typename T, typename ...Args> inline void write(T x, Args ...args) {write(x),write(args...);}
}using IO::write; using IO::read;

const int N=2e5+10,INF=0x3f3f3f3f;
struct node{
    int mx,mn,ltor,rtol;
    node(){mx=-INF;mn=INF;ltor=rtol=0;}
    node(int mx,int mn,int ltor,int rtol){this->mx=mx;this->mn=mn;this->ltor=ltor;this->rtol=rtol;}
    void merge(const node &y){
        ltor=max({ltor,y.ltor,y.mx-mn});
        rtol=max({rtol,y.rtol,mx-y.mn});
        mx=max(mx,y.mx);
        mn=max(mn,y.mn);
    }
    friend node merge(const node &x,const node &y){
        node res;
        res.merge(x);res.merge(y);
        return res;
    }
};
int head[N],to[N],nex[N],a[N];
int mx[N<<2],mn[N<<2],ltor[N<<2],rtol[N<<2],tag[N<<2];
int top[N],son[N],sz[N],dp[N],fa[N],id[N],val[N];
int n,q,tot,cnt;
void add(int u,int v){
    nex[++tot]=head[u];
    to[tot]=v;
    head[u]=tot;
}
//我保证dfs都是对的 ，请不要在意奇怪的写法 
void dfs1(int x,int f,int deep){
    fa[x]=f;dp[x]=deep;sz[x]=1;int mx=-1;
    for(int i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==f)continue;
        dfs1(y,x,deep+1);
        sz[x]+=sz[y];
        mx<sz[y]&&(mx=sz[y],son[x]=y); 
    }
}
void dfs2(int x,int topf){
    top[x]=topf;id[x]=++cnt;val[cnt]=a[x];
    if(!son[x])return;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa[x]||y==son[x])continue;
        dfs2(y,y);
    }
}
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}
void push_up(int p){
    mx[p]=max(mx[ls(p)],mx[rs(p)]);
    mn[p]=min(mn[ls(p)],mn[rs(p)]);
    ltor[p]=max({ltor[ls(p)],ltor[rs(p)],mx[rs(p)]-mn[ls(p)]});
    rtol[p]=max({rtol[ls(p)],rtol[rs(p)],mx[ls(p)]-mn[rs(p)]});
}
void fix(int p,int k){
    mn[p]+=k;mx[p]+=k;tag[p]+=k;
}
void push_down(int p){
    fix(ls(p),tag[p]);fix(rs(p),tag[p]);
    tag[p]=0;
}
void build(int l=1,int r=n,int p=1){
    if(l==r){mx[p]=mn[p]=val[l];return;}
    int mid=l+r>>1;
    build(l,mid,ls(p));
    build(mid+1,r,rs(p));
    push_up(p);
}
void update(int x,int y,int k,int l=1,int r=n,int p=1){
    if(x<=l&&r<=y){fix(p,k);return;}
    int mid=l+r>>1;push_down(p);
    if(x<=mid)update(x,y,k,l,mid,ls(p));
    if(y>mid)update(x,y,k,mid+1,r,rs(p));
    push_up(p);
}
node query(int x,int y,int l=1,int r=n,int p=1){
    if(x<=l&&r<=y)return {mx[p],mn[p],ltor[p],rtol[p]};
    int mid=l+r>>1;push_down(p);
    if(y<=mid)return query(x,y,l,mid,ls(p));
    if(x>mid)return query(x,y,mid+1,r,rs(p));
    return merge(query(x,y,l,mid,ls(p)),query(x,y,mid+1,r,rs(p)));
}
void rUpdate(int x,int y,int k){
    if(top[x]^top[y]){
        if(dp[top[x]]<dp[top[y]])swap(x,y);
        update(id[top[x]],id[x],k);
        x=fa[top[x]];
    }
    if(dp[x]>dp[y])swap(x,y);
    update(id[x],id[y],k);
}
int rQuery(int x,int y){
    node l,r;
    while(top[x]^top[y]){
        if(dp[top[x]]<dp[top[y]]){
            r.merge(query(id[top[y]],id[y]));
            y=fa[top[y]];
        }else{
            l.merge(query(id[top[x]],id[x]));
            x=fa[top[x]];
        }
    }
    if(dp[x]>dp[y])l.merge(query(id[y],id[x]));
    else r.merge(query(id[x],id[y]));
    return max({r.ltor,l.rtol,r.mx-l.mn,0});
}
int main(){
    int i,j,k,u,v,w;
    freopen("P3976.in","r",stdin);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //请不要在意循环的写法，我确保他是正确的 
    for(read(n),i=0;++i<=n;)read(a[i]);
    for(i=0;++i<n;)read(u,v),add(u,v),add(v,u);
    dfs1(1,0,1);dfs2(1,1);build();
    for(read(q);q--;){
        read(u,v,w);
        write(rQuery(u,v),"\n");
        rUpdate(u,v,w);
    }
    return 0;
}