https://www.luogu.com.cn/problem/P3976

#include <bits/stdc++.h>
const int MAXN=5e4+5;
using namespace std;
struct Segment_tree{
	int maxx,minn,lm,rm;
}t[4*MAXN];
int son[MAXN],id[MAXN],dep[MAXN],fa[MAXN],top[MAXN],cnt,w[MAXN],wt[MAXN],size[MAXN],n,lazy[4*MAXN];
vector<int> G[MAXN];
void pushup(int p){
	t[p].maxx=max(t[2*p].maxx,t[2*p+1].maxx);
	t[p].minn=min(t[2*p].minn,t[2*p+1].minn);
	t[p].lm=max(max(t[2*p].lm,t[2*p+1].lm),t[2*p].maxx-t[2*p+1].minn);
	t[p].rm=max(max(t[2*p].rm,t[2*p+1].rm),t[2*p+1].maxx-t[2*p].minn);
}
Segment_tree getin(Segment_tree a,Segment_tree b){
	Segment_tree c;
	c.minn=min(a.minn,b.minn);
	c.maxx=max(a.maxx,b.maxx);
	c.lm=max(max(a.lm,b.lm),a.maxx-b.minn);
	c.rm=max(max(a.rm,b.rm),b.maxx-a.minn);
	return c;
}
void pushdown(int p){
	int k=lazy[p];
	lazy[p]=0;
	t[2*p].maxx+=k;
	t[2*p].minn+=k;
	lazy[2*p]+=k;
	t[2*p+1].maxx+=k;
	t[2*p+1].minn+=k;
	lazy[2*p+1]+=k;
}
void build(int p,int l,int r){
	if(l==r){
		t[p].maxx=w[l];
		t[p].minn=w[l];
		return ;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	pushup(p);
}
void update(int p,int l,int r,int L,int R,int k){
	if(L<=l&&r<=R){
		t[p].maxx+=k;
		t[p].minn+=k;
		lazy[p]+=k;
		return ;
	}
	int mid=(l+r)/2;
	if(lazy[p]) pushdown(p);
	if(L<=mid) update(2*p,l,mid,L,R,k);
	if(R>mid) update(2*p+1,mid+1,r,L,R,k);
	pushup(p);
} 
Segment_tree query(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return t[p];
	}
	int mid=(l+r)/2;
	if(lazy[p]) pushdown(p);
	if(R<=mid) return query(p*2,l,mid,L,R);
	if(L>mid) return query(p*2+1,mid+1,r,L,R);
	return getin(query(p*2,l,mid,L,R),query(p*2+1,mid+1,r,L,R));
}
void dfs1(int x,int last,int deep){
	dep[x]=deep;
	fa[x]=last;
	size[x]=1;
	int len=G[x].size();
	for(int i=0;i<len;i++){
		int y=G[x][i];
		if(y==last) continue;
		dfs1(y,x,deep+1);
		size[x]+=size[y];
		if(size[y]>size[son[x]]) son[x]=y;
	}
} 
void dfs2(int x,int topf){
	id[x]=++cnt;
	w[cnt]=wt[x];
	top[x]=topf;
	if(!son[x]) return ;
	dfs2(son[x],topf);
	int len=G[x].size();
	for(int i=0;i<len;i++){
		int y=G[x][i];
		if(y!=fa[x]&&y!=son[x]){
			dfs2(y,y);
		}
	}
}
void uprange(int x,int y,int k){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		update(1,1,n,id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	update(1,1,n,id[x],id[y],k);
}
int qrange(int x,int y){
	Segment_tree l,r;
	l.minn=r.minn=0x3f3f3f3f;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]){
			r=getin(query(1,1,n,id[top[y]],id[y]),r);
			y=fa[top[y]];
		}else{
			l=getin(query(1,1,n,id[top[x]],id[x]),l);
			x=fa[top[x]];
		}
	}
	if(dep[x]>dep[y]) l=getin(query(1,1,n,id[y],id[x]),l);
	else r=getin(query(1,1,n,id[x],id[y]),r);
	swap(l.lm,l.rm);
	return getin(l,r).rm;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&wt[i]);
	}
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs1(1,0,1),dfs2(1,1);
	build(1,1,n);
	int q;
	scanf("%d",&q);
	while(q--){
		int x,y,c;
		scanf("%d %d %d",&x,&y,&c);
		printf("%d\n",qrange(x,y));
		uprange(x,y,c);
	}
	return 0;
}