树链剖分+线段树
线段树维护max，min，左往右的最大差，右往左的最大差
求LCA时一定要注意方向
# include <bits/stdc++.h>
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int _(1e5 + 10), INF(1e9);
IL ll Read(){
char c = '%'; ll x = 0, z = 1;
for(; c > '9' || c < '0'; c = getchar()) if(c == '-') z = -1;
for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
return x * z;
}
int n, cnt, fst[_], to[_], nxt[_], fa[_], son[_], size[_], top[_], deep[_], dfn[_], w[_], id[_], tag[_ << 2];
struct Data{
int lr, rl, mx, mn;
IL void Init(){ lr = rl = mx = -INF; mn = INF; }
} t[_ << 2];
IL void Add(RG int u, RG int v){ to[cnt] = v; nxt[cnt] = fst[u]; fst[u] = cnt++; }
IL void Dfs1(RG int u){
size[u] = 1;
for(RG int e = fst[u]; e != -1; e = nxt[e]){
if(size[to[e]]) continue;
deep[to[e]] = deep[u] + 1; fa[to[e]] = u;
Dfs1(to[e]);
size[u] += size[to[e]];
if(size[to[e]] > size[son[u]]) son[u] = to[e];
}
}
IL void Dfs2(RG int u, RG int Top){
top[u] = Top; dfn[u] = ++cnt; id[cnt] = u;
if(son[u]) Dfs2(son[u], Top);
for(RG int e = fst[u]; e != -1; e = nxt[e])
if(!dfn[to[e]]) Dfs2(to[e], to[e]);
}
IL Data Merge(RG Data A, RG Data B){
RG Data C; C.Init();
C.mx = max(A.mx, B.mx); C.mn = min(A.mn, B.mn);
C.lr = max(max(A.lr, B.lr), B.mx - A.mn);
C.rl = max(max(A.rl, B.rl), A.mx - B.mn);
return C;
}
# define lson x << 1, l, mid
# define rson x << 1 | 1, mid + 1, r
IL void Pushdown(RG int x){
if(!tag[x]) return;
RG int ls = x << 1, rs = x << 1 | 1;
t[ls].mx += tag[x]; t[ls].mn += tag[x]; tag[ls] += tag[x];
t[rs].mx += tag[x]; t[rs].mn += tag[x]; tag[rs] += tag[x];
tag[x] = 0;
}
IL void Build(RG int x, RG int l, RG int r){
if(l == r){ t[x].mx = t[x].mn = w[id[l]]; return; }
RG int mid = (l + r) >> 1;
Build(lson); Build(rson);
t[x] = Merge(t[x << 1], t[x << 1 | 1]);
}
IL Data Query(RG int x, RG int l, RG int r, RG int L, RG int R, RG int v){
RG Data ans; ans.Init();
if(L <= l && R >= r){
ans = t[x]; t[x].mx += v; t[x].mn += v; tag[x] += v;
return ans;
}
Pushdown(x);
RG int mid = (l + r) >> 1;
if(L <= mid) ans = Query(lson, L, R, v);
if(R > mid) ans = Merge(ans, Query(rson, L, R, v));
t[x] = Merge(t[x << 1], t[x << 1 | 1]);
return ans;
}
IL void Cover(RG int x, RG int y, RG int v){
RG Data ansl, ansr; ansl.Init(); ansr.Init();
while(top[x] != top[y]){
if(deep[top[x]] > deep[top[y]]) ansl = Merge(Query(1, 1, n, dfn[top[x]], dfn[x], v), ansl), x = fa[top[x]];
else ansr = Merge(Query(1, 1, n, dfn[top[y]], dfn[y], v), ansr), y = fa[top[y]];
}
RG Data Max; swap(ansl.lr, ansl.rl);
if(dfn[x] < dfn[y]){
ansl = Merge(ansl, Query(1, 1, n, dfn[x], dfn[y], v));
Max = Merge(ansl, ansr);
}
else{
Max = Query(1, 1, n, dfn[y], dfn[x], v); swap(Max.lr, Max.rl);
ansr = Merge(Max, ansr); Max = Merge(ansl, ansr);
}
printf("%d
", Max.lr > 0 ? Max.lr : 0);
}
int main(RG int argc, RG char *argv[]){
n = Read();
for(RG int i = 1; i <= n; i++) w[i] = Read(), fst[i] = -1;
for(RG int i = 1, a, b; i < n; i++) a = Read(), b = Read(), Add(a, b), Add(b, a);
Dfs1(1); cnt = 0; Dfs2(1, 1); Build(1, 1, n);
for(RG int Q = Read(), a, b, v; Q; Q--) a = Read(), b = Read(), v = Read(), Cover(a, b, v);
return 0;
}