题目链接
参考代码（树链剖分）

#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[1000006];
struct oppo{
    int to,next;
}rood[2000006];
int head[1000006],tot_;
void add(int from,int to)//建边 
{
    rood[++tot_].to=to;
    rood[tot_].next=head[from];
    head[from]=tot_;
}
int to[1000006],deep[1000006];
/*
to:重边
deep：深度（下标为节点） 
*/ 
void dfs1(int x,int fa)
{
    deep[x]=1;
    for(int i=head[x];i;i=rood[i].next){
        if(rood[i].to==fa)
            continue;
        dfs1(rood[i].to,x);
        if(deep[rood[i].to]+1>deep[x]){
            deep[x]=deep[rood[i].to]+1;
            to[x]=rood[i].to;
        }
    }
}
int tot,bh[1000006],fbh[1000006],dep[1000006],father[1000006],ha[10000006];
/*
bh:节点的编号
fbh:编号对应的节点
dep:深度（下标为编号）
father:父亲 （下标为编号  值也是编号） 
ha:链的最高点的编号 
*/
void dfs2(int x,int fa)
{
    bh[x]=++tot;
    fbh[tot]=x;
    if(to[x]){
        dep[tot+1]=dep[bh[x]]+1;
        ha[tot+1]=ha[bh[x]];
        father[tot+1]=bh[x];
        dfs2(to[x],x);
    }
    for(int i=head[x];i;i=rood[i].next){
        if(rood[i].to==fa||rood[i].to==to[x])
            continue;
        father[tot+1]=bh[x];
        dep[tot+1]=dep[bh[x]]+1;
        dfs2(rood[i].to,x);
    }
}
void work()//树链剖分 
{
    dfs1(1,0);
    dep[1]=1;
    for(int i=1;i<=n;i++)
        ha[i]=i;
    dfs2(1,0);
}
int MAX[4000006],MIN[4000006],to1[4000006],to2[4000006],lazy[4000006];
/*
MAX:线段树最大值 
MIN:线段树最小值 
to1:一条链  从上到下获利最大值 
to2:一条链  从下到上获利最大值 
lazy:add函数的懒标记 
*/
void update(int x)
{
    MAX[x]=max(MAX[x*2],MAX[x*2+1]);
    MIN[x]=min(MIN[x*2],MIN[x*2+1]);
    to1[x]=max(MAX[x*2+1]-MIN[x*2],max(to1[x*2],to1[x*2+1]));
    to2[x]=max(MAX[x*2]-MIN[x*2+1],max(to2[x*2],to2[x*2+1]));
}
void Mark_down(int x)
{
    if(lazy[x])
    {
        lazy[x*2]+=lazy[x];
        lazy[x*2+1]+=lazy[x];
        MAX[x*2]+=lazy[x];
        MIN[x*2]+=lazy[x];
        MAX[x*2+1]+=lazy[x];
        MIN[x*2+1]+=lazy[x];
        lazy[x]=0;
    }
}
void buit(int x,int l,int r)
{
    if(l==r){
        MAX[x]=MIN[x]=v[fbh[l]];
        return;
    }
    int mid=(l+r)/2;
    buit(x*2,l,mid);
    buit(x*2+1,mid+1,r);
    update(x);
}
struct vivo{
    int MAX,MIN;
    int to1,to2;
}st;
void csh(vivo &x)//初始化变量 
{
    x.MAX=x.to1=x.to2=0;
    x.MIN=INT_MAX;
}
vivo merge(vivo a,vivo b)//合并 
{
    vivo c;
    c.MAX=max(a.MAX,b.MAX);
    c.MIN=min(a.MIN,b.MIN);
    c.to1=max(b.MAX-a.MIN,max(a.to1,b.to1));
    c.to2=max(a.MAX-b.MIN,max(a.to2,b.to2));
    return c;        
}
vivo ask(int x,int ll,int lr,int l,int r)
{
    Mark_down(x);
    if(ll<=l&&r<=lr){
        st.MAX=MAX[x];
        st.MIN=MIN[x];
        st.to1=to1[x];
        st.to2=to2[x];
        return st;  
    }
    int mid=(l+r)/2;
    vivo a1,a2;
    csh(a1);csh(a2);
    if(ll<=mid)
        a1=ask(x*2,ll,lr,l,mid);
    if(lr>mid)
        a2=ask(x*2+1,ll,lr,mid+1,r);
    st=merge(a1,a2);
    update(x);
    return st;
}
int lll;
void add(int x,int ll,int lr,int l,int r)
{
    Mark_down(x);
    if(ll<=l&&r<=lr){
        MAX[x]+=lll;
        MIN[x]+=lll;
        lazy[x]+=lll;
        return; 
    }
    int mid=(l+r)/2;
    if(ll<=mid)
        add(x*2,ll,lr,l,mid);
    if(lr>mid)
        add(x*2+1,ll,lr,mid+1,r);
    update(x);
}
int s,t;
void work_out()
{
    buit(1,1,n);
    cin>>m;
    while(m--)
    {
        vivo all1,all2;
        csh(all1);csh(all2);
        scanf("%d %d %d",&s,&t,&lll);
        s=bh[s];
        t=bh[t];
        int ss=s,tt=t;
        /*
            首先找到两个点的最近公共祖先
            两个点分别向上跳
            答案统计在 all1  all2 里
            分类讨论最后两个点跳到同一个链上
            处理 all1 all2 即为ANS 
        */ 
        while(ha[s]!=ha[t])
        {
            if(dep[ha[s]]>dep[ha[t]])
                s=father[ha[s]];
            else
                t=father[ha[t]];
        }
        int lca=min(s,t);
        s=ss;t=tt;
        while(ha[s]!=ha[lca]){
            vivo k=ask(1,ha[s],s,1,n);
            add(1,ha[s],s,1,n);
            all1=merge(k,all1);
            s=father[ha[s]];
        }
        while(ha[t]!=ha[lca]){
            vivo k=ask(1,ha[t],t,1,n);
            add(1,ha[t],t,1,n);
            all2=merge(k,all2);
            t=father[ha[t]];
        }
        if(t==lca){ 
            all1=merge(ask(1,t,s,1,n),all1);
            add(1,t,s,1,n);
        }
        else{
            all2=merge(ask(1,s,t,1,n),all2);
            add(1,s,t,1,n);
        }
        int ANS=max(all2.MAX-all1.MIN,max(all1.to2,all2.to1));
        printf("%d\n",ANS);
    }
}
int main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<n;i++){
        scanf("%d %d",&s,&t);
        add(s,t);add(t,s);
    }
    work();
    work_out();
    return 0;
}