写的树剖，两个小样例都过了，交上去WA 10

调一天了/kk

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll re_ad() {
	char ch=getchar(); ll x=0,f=1;
	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
	while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x*f;
}

const ll N=1e5+11,M=N<<1,Tree_Sz=N<<2,mod=1e9+7,inf=1e18;
ll n,m,a[N];
ll to[M],nxt[M],edge,head[N];
ll fa[N],dep[N],siz[N],son[N],top[N],tot,seg[N],rev[N];
inline void addedge(ll x,ll y) {
	++edge,to[edge]=y,nxt[edge]=head[x],head[x]=edge;
	++edge,to[edge]=x,nxt[edge]=head[y],head[y]=edge;
}

void dfs1(ll d,ll f) {
	fa[d]=f,siz[d]=1,dep[d]=dep[f]+1;
	for(ll i=head[d];i;i=nxt[i]) if(to[i]!=f) { dfs1(to[i],d),siz[d]+=siz[to[i]]; if(siz[to[i]]>siz[son[d]]) son[d]=to[i]; }
}
void dfs2(ll d,ll f) {
	top[d]=f,seg[d]=++tot,rev[tot]=a[d]; if(son[d]) dfs2(son[d],f);
	for(ll i=head[d];i;i=nxt[i]) if(to[i]!=fa[d] && to[i]!=son[d]) dfs2(to[i],to[i]);
}

namespace ST {
	struct Node {
		ll mx,mn,l,r,tag;
		Node() { mx=l=r=tag=0,mn=1e18; }
		void add(ll d) { mx+=d,mn+=d,tag+=d; }
		void print() { printf("%lld %lld %lld %lld %lld\n",mx,mn,l,r,tag); }
		Node operator + (const Node &B) const {
			Node res; res.mx=max(mx,B.mx),res.mn=min(mn,B.mn);
			res.l=max(mx-B.mn,max(l,B.l)),res.r=max(B.mx-mn,max(r,B.r)); return res;
		}
	} t[Tree_Sz];
	inline void Pushup(ll d) { t[d]=t[d<<1]+t[d<<1|1]; }
	inline void Pushdown(ll d) { if(t[d].tag) t[d<<1].add(t[d].tag),t[d<<1|1].add(t[d].tag),t[d].tag=0; }
	void build(ll d,ll l,ll r) { 
		if(l==r) { t[d].mx=t[d].mn=a[rev[l]]; return ; }
		ll mid=(l+r)>>1; build(d<<1,l,mid),build(d<<1|1,mid+1,r); Pushup(d);
	}
	inline void Build() { build(1,1,n); }
	void modify(ll d,ll l,ll r,ll x,ll y,ll z) {
		if(x<=l && r<=y) { t[d].add(z); return ; }
		ll mid=(l+r)>>1; Pushdown(d);
		if(x<=mid) modify(d<<1,l,mid,x,y,z);
		if(y>=mid+1) modify(d<<1|1,mid+1,r,x,y,z);
		Pushup(d);
	}
	inline void Modify(ll x,ll y,ll z) { modify(1,1,n,x,y,z); }
	Node query(ll d,ll l,ll r,ll x,ll y) {
		if(x<=l && r<=y) return t[d];
		ll mid=(l+r)>>1; Pushdown(d);
		if(x>mid) return query(d<<1|1,mid+1,r,x,y);
		if(y<=mid) return query(d<<1,l,mid,x,y);
		return query(d<<1,l,mid,x,y)+query(d<<1|1,mid+1,r,x,y);
	}
	inline Node Query(ll x,ll y) { return query(1,1,n,x,y); }
	void tprint(ll d,ll l,ll r) {
		printf("%lld %lld %lld: ",d,l,r); t[d].print(); if(l==r) return ;
		ll mid=(l+r)>>1; tprint(d<<1,l,mid),tprint(d<<1|1,mid+1,r);
	}
	inline void Tprint() { tprint(1,1,n); }
}

inline void Update(ll x,ll y,ll z) {
	while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]]) x^=y^=x^=y; ST::Modify(seg[top[x]],seg[x],z),x=fa[top[x]]; }
	if(dep[x]>dep[y]) x^=y^=x^=y; ST::Modify(seg[x],seg[y],z);
}
inline void Ask(ll x,ll y) {
	ST::Node resl,resr;
	while(top[x]!=top[y]) {
		if(dep[top[x]]<dep[top[y]]) resr=ST::Query(seg[top[y]],seg[y])+resr,y=fa[top[y]];
		else resl=ST::Query(seg[top[x]],seg[x])+resl,x=fa[top[x]];
	}
	if(dep[x]>dep[y]) resl=ST::Query(seg[y],seg[x])+resl;
	else resr=ST::Query(seg[x],seg[y])+resr;
	resl.l^=resl.r^=resl.l^=resl.r; printf("%lld\n",(resl+resr).r);
//	printf("%lld %lld: \n",x,y); resl.print(); resr.print(); (resl+resr).print();
//	ST::Tprint(); puts("");
}

int main()
{
//	freopen("P3976_2.in","r",stdin);
//	freopen("P3976.out","w",stdout);
	n=re_ad();
	for(ll i=1;i<=n;++i) a[i]=re_ad();
	for(ll i=1,x,y;i<n;++i) x=re_ad(),y=re_ad(),addedge(x,y);
	dfs1(1,0); dfs2(1,1); ST::Build();
	m=re_ad();
//	for(ll i=1;i<=n;++i) printf("%lld ",dep[i]); puts("");
//	for(ll i=1;i<=n;++i) printf("%lld ",top[i]); puts("");
//	for(ll i=1;i<=n;++i) printf("%lld ",seg[i]); puts("");
//	for(ll i=1;i<=n;++i) printf("%lld ",rev[i]); puts("");
	for(ll x,y,z;m--;) x=re_ad(),y=re_ad(),z=re_ad(),Ask(x,y),Update(x,y,z);
	return 0;
}