思路是维护区间最大值 mx，最小值 mn，从左到右走的最大值 ls，从右到左走的最大值 rs。

测评记录：https://www.luogu.com.cn/record/105832287

#include <bits/stdc++.h>
using namespace std;
namespace Milkcat {
	typedef long long LL;
	const int N = 1e6 + 5, inf = 1e9;
	LL n, q, rt, mod, opt, u, v, x, a[N];
	struct SegmentTree {
		struct node {
			LL mx, mn, ls, rs;
			node(LL _1 = 0, LL _2 = 0, LL _3 = 0, LL _4 = 0) :
				mx(_1), mn(_2), ls(_3), rs(_4) {}
			node operator *= (int x) { mx += x, mn += x; }
			node operator + (node qwq) {
				node res;
				res.ls = max({ls, qwq.ls, qwq.mx - mn});
				res.rs = max({rs, qwq.rs, mx - qwq.mn});
				res.mx = max(mx, qwq.mx), res.mn = min(mn, qwq.mn);
				return res;
			}
		} sum[N << 1];
	    LL cnt, tag[N << 1], Ls[N << 1], Rs[N << 1];
	    inline int ls(int p) { return Ls[p] ? Ls[p] : Ls[p] = ++ cnt; }
	    inline int rs(int p) { return Rs[p] ? Rs[p] : Rs[p] = ++ cnt; }
	    inline void push_up(int p) { sum[p] = sum[ls(p)] + sum[rs(p)]; }
	    void push_down(int p, int l, int r) {
	        int mid = (l + r) >> 1;
	        tag[ls(p)] += tag[p], sum[ls(p)] *= tag[p];
	        tag[rs(p)] += tag[p], sum[rs(p)] *= tag[p];
	        tag[p] = 0;
	    }
	    void modify(int p, int l, int r, int nl, int nr, LL k) {
	        if (nl <= l && r <= nr) { tag[p] += k, sum[p] *= k; return; }
			push_down(p, l, r);
	        int mid = (l + r) >> 1;
	        if (nl <= mid) modify(ls(p), l, mid, nl, nr, k);
	        if (nr > mid) modify(rs(p), mid + 1, r, nl, nr, k);
	        push_up(p);
		}
	    node query(int p, int l, int r, int nl, int nr) {
	        if (nl <= l && r <= nr) {
	        	return sum[p];
	        }
	        push_down(p, l, r);
	        LL mid = (l + r) >> 1;
	        if (nl <= mid && mid < nr)
				return query(ls(p), l, mid, nl, nr) + query(rs(p), mid + 1, r, nl, nr);
	        if (nl <= mid) return query(ls(p), l, mid, nl, nr);
	        if (nr > mid) return query(rs(p), mid + 1, r, nl, nr);
	    }
	    SegmentTree() { cnt = 1; }
	} Sgt;
	struct TreeDecom {
		LL tot, depth[N], fa[N], siz[N], son[N], top[N], id[N];
		vector<int> G[N];
		void add(int u, int v) {
			G[u].push_back(v), G[v].push_back(u);
		}
		void dfs1(int u, int fat) {
			fa[u] = fat, siz[u] = 1, depth[u] = depth[fa[u]] + 1;
			for (int v : G[u]) {
				if (v == fa[u]) continue;
				dfs1(v, u), siz[u] += siz[v];
				if (!son[u] || siz[v] > siz[son[u]])
					son[u] = v;
			}
		}
		void dfs2(int u, int topf) {
			top[u] = topf, id[u] = ++ tot;
			Sgt.modify(1, 1, n, id[u], id[u], a[u]);
			if (son[u]) dfs2(son[u], topf);
			for (int v : G[u]) {
				if (v == fa[u] || v == son[u]) continue;
				dfs2(v, v);
			}
		}
		void updRange(int u, int v, int k) {
			while (top[u] != top[v]) {
				if (depth[top[u]] < depth[top[v]]) swap(u, v);
				Sgt.modify(1, 1, n, id[top[u]], id[u], k), u = fa[top[u]];
			}
			if (depth[u] > depth[v]) swap(u, v);
			Sgt.modify(1, 1, n, id[u], id[v], k);
		}
		int qRange(int u, int v) {
			SegmentTree::node ans1(-inf, inf, -inf, -inf), ans2 = ans1;
			while (top[u] != top[v]) {
//				cout << u << ' ' << v << '\n';
				if (depth[top[u]] < depth[top[v]])
					ans2 = ans2 + Sgt.query(1, 1, n, id[top[v]], id[v]), v = fa[top[v]]; 
				else ans1 = ans1 + Sgt.query(1, 1, n, id[top[u]], id[u]), u = fa[top[u]]; 
			}
			if (depth[u] < depth[v]) ans1 = ans1 + Sgt.query(1, 1, n, id[u], id[v]);
			else ans2 = ans2 + Sgt.query(1, 1, n, id[v], id[u]);
			return max({ans1.ls, ans2.rs, ans2.mx - ans1.mn});
		}
	} T;
	int main() {
		ios::sync_with_stdio(0);
		cin.tie(0), cout.tie(0);
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		for (int i = 1; i < n; i ++) cin >> u >> v, T.add(u, v);
		cin >> q, T.dfs1(1, 0), T.dfs2(1, 1);
		for (int i = 1; i <= q; i ++) {
			cin >> u >> v >> x;
			cout<< max(T.qRange(u, v), 0) << '\n';
			T.updRange(u, v, x);
		}
		return 0;
	}
}
int main() {
	return Milkcat::main();
}