如题

#include<cstdio>
#include<algorithm>
#define ls pos<<1
#define rs pos<<1|1
#define mid (t[pos].l+t[pos].r>>1)
using namespace std;
typedef long long ll;
const int maxn=50005;
const int inf=int(2e9);
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
	while(c>=48&&c<=57){x=(x<<1)+(x<<3)+c-48;c=getchar();}
	return f==1?x:-x;
}
int n,m,ecnt,head[maxn],a[maxn];
struct edge_node{
	int to,nxt;
}ed[maxn<<1];
inline void adde(int u,int v){
	ed[++ecnt]=edge_node{v,head[u]},head[u]=ecnt;
}inline void add(int u,int v){
	adde(u,v),adde(v,u);
}
int f[maxn],dep[maxn],siz[maxn],ss[maxn];
int scnt,dfn[maxn],from[maxn],top[maxn];
int dfs(int x,int fa){
	f[x]=fa,dep[x]=dep[fa]+1,siz[x]=1;
	for(int i=head[x];i;i=ed[i].nxt){
		if(ed[i].to!=fa){
			siz[x]+=dfs(ed[i].to,x);
			if(siz[ed[i].to]>siz[ss[x]])
				ss[x]=ed[i].to;
		}
	}
	return siz[x];
}
void dfs1(int x,int st){
	dfn[x]=++scnt,from[scnt]=x,top[x]=st;
	if(ss[x])dfs1(ss[x],st);
	for(int i=head[x];i;i=ed[i].nxt)
		if(ed[i].to!=f[x]&&ed[i].to!=ss[x])
			dfs1(ed[i].to,ed[i].to);
}
struct segt_node{
	int l,r,mn,mx,x,upd;
}t[maxn<<2];
inline void push_down(int pos){
	if(t[pos].upd){
		t[ls].mn+=t[pos].upd,t[ls].mx+=t[pos].upd;
		t[rs].mn+=t[pos].upd,t[rs].mx+=t[pos].upd;
		t[ls].upd+=t[pos].upd,t[rs].upd+=t[pos].upd;
		t[pos].upd=0;
	}
}
inline void push_up(int pos){
	t[pos].mn=min(t[ls].mn,t[rs].mn);
	t[pos].mx=max(t[ls].mx,t[rs].mx);
	t[pos].x=max(t[rs].mx-t[ls].mn,max(t[ls].x,t[rs].x));
}
void build(int pos,int l,int r){
	t[pos].l=l,t[pos].r=r;
	if(l==r){
		t[pos].mn=t[pos].mx=a[from[l]];
		return;
	}
	build(ls,l,mid),build(rs,mid+1,r);
	push_up(pos);
}
void update(int pos,int l,int r,int val){
	if(t[pos].l>=l&&t[pos].r<=r){
		t[pos].mn+=val,t[pos].mx+=val;
		t[pos].upd+=val;return;
	}
	push_down(pos);
	if(l<=mid)update(ls,l,r,val);
	if(r>mid)update(rs,l,r,val);
	push_up(pos);
}
struct Node{
	int mn,mx,x;
}now;
Node query(int pos,int l,int r){
	if(t[pos].l>=l&&t[pos].r<=r)
		return Node{t[pos].mn,t[pos].mx,t[pos].x};
	if(t[pos].l>r||t[pos].r<l)return Node{0,0,0};
	push_down(pos);
	Node x1=query(ls,l,r),x2=query(rs,l,r);
	if(!x1.mn)return x2;if(!x2.mn)return x1;
	Node x=Node{min(x1.mn,x2.mn),max(x1.mx,x2.mx),0};
	x.x=max(x2.mx-x1.mn,max(x1.x,x2.x));return x;
}
int querymn(int pos,int l,int r){
	if(t[pos].l>=l&&t[pos].r<=r)return t[pos].mn;
	if(t[pos].l>r||t[pos].r<l)return inf;
	push_down(pos);
	return min(querymn(ls,l,r),querymn(rs,l,r));
}
int querymx(int pos,int l,int r){
	if(t[pos].l>=l&&t[pos].r<=r)return t[pos].mx;
	if(t[pos].l>r||t[pos].r<l)return -inf;
	push_down(pos);
	return max(querymx(ls,l,r),querymx(rs,l,r));
}
int mx,L,R,premn[maxn],sufmx[maxn],premn1[maxn],sufmx1[maxn];
inline int lca_query(int x,int y){
	mx=0;L=0,R=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]){
			now=query(1,dfn[top[x]],dfn[x]),mx=max(mx,now.x);
			premn[++L]=querymn(1,dfn[top[x]],dfn[x]);
			sufmx[L]=querymx(1,dfn[top[x]],dfn[x]);
			x=f[top[x]];
		}else{
			now=query(1,dfn[top[y]],dfn[y]),mx=max(mx,now.x);
			premn1[++R]=querymn(1,dfn[top[y]],dfn[y]);
			sufmx1[R]=querymx(1,dfn[top[y]],dfn[y]);
			y=f[top[y]];
		}
	}
	if(dep[x]<dep[y])swap(x,y);
	now=query(1,dfn[y],dfn[x]),mx=max(mx,now.x);
	premn[++L]=querymn(1,dfn[y],dfn[x]);
	sufmx[L]=querymx(1,dfn[y],dfn[x]);
	for(int i=1;i<=R;++i)premn[L+i]=premn1[R-i+1],sufmx[L+i]=sufmx[R-i+1];
	for(int i=2,K=L+R;i<=K;++i)premn[i]=min(premn[i],premn[i-1]);
	for(int i=L+R-1;i;--i)sufmx[i]=max(sufmx[i],sufmx[i+1]);
	for(int i=1,K=L+R;i<K;++i)mx=max(mx,sufmx[i+1]-premn[i]);
	return mx;
}
inline void lca_update(int x,int y,ll val){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])
			swap(x,y);
		update(1,dfn[top[x]],dfn[x],val);
		x=f[top[x]];
	}
	if(dep[x]<dep[y])swap(x,y); 
	update(1,dfn[y],dfn[x],val);
}
int main(){
	n=read();
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1,x,y;i<n;++i){
		x=read(),y=read();add(x,y);
	}
	dfs(1,0),dfs1(1,1);
	build(1,1,n);
	m=read();int x,y,z;
	while(m--){
		x=read(),y=read(),z=read();
		printf("%d\n",lca_query(x,y));
		lca_update(x,y,z);
	}
	return 0;
}
/*
5
1 2 3 4 5
1 2
1 3
2 4
4 5
6
1 5 50
2 4 500
3 4 5000
3 5 50000
1 3 500000
2 3 5000000

4
2
551
551
0
499499
*/