树链剖分+线段树

线段树维护max，min，左往右的最大差，右往左的最大差

求LCA时一定要注意方向

# include 
     
      # 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, rIL 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\n", 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;}