题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=4127

题解

首先区间绝对值和可以转化为 \(2\) 倍的区间正数和 \(-\) 区间和。于是问题就转化为区间正数和。

因为每一次增加的量 \(d \geq 0\)，所以每一个数只会被从负数变成正数一次。也就是说，从负变正的操作最多出现 \(n\) 次。

于是我们考虑在线段树上对于从负数变成正数的操作暴力修改。

如何判断一个区间内有负数变成正数的操作呢。令 \(c\) 表示这个区间的最大负数。于是如果 \(-k \leq c \leq 0\) 那么说明区间有数从负变正。

那么每一次从负变正都会走 \(\log n\) 个线段树节点，于是所有数从负变正而来的总时间为 \(O(n\log n)\)。

其余的修改的复杂度为 \(O(q\log n)\)。

---

时间复杂度为 \(O((n+q)\log n)\)。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b , 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b , 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

#define lc o << 1

#define rc o << 1 | 1

const int N = 1e5 + 7;

const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, m, dfc;

int a[N];

int dep[N], f[N], siz[N], son[N], dfn[N], pre[N], top[N];

struct Edge { int to, ne; } g[N << 1]; int head[N], tot;

inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }

inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }

struct Node { ll sum, add, sumc, maxf; int s; } t[N << 2];

inline void pushup(int o, int L, int R) {

	t[o].s = t[lc].s + t[rc].s;

	t[o].sum = t[lc].sum + t[rc].sum + t[o].add * (R - L + 1);

	t[o].sumc = t[lc].sumc + t[rc].sumc + t[o].add * t[o].s;

	t[o].maxf = -INF;

	if (t[lc].maxf) smax(t[o].maxf, t[lc].maxf);

	if (t[rc].maxf) smax(t[o].maxf, t[rc].maxf);

	if (t[o].maxf == -INF) t[o].maxf = 0;

	t[o].maxf && (t[o].maxf += t[o].add);

	// dbg("o = %d, L = %d, R = %d, t[o].maxf = %lld, t[o].s = %d\n", o, L, R, t[o].maxf, t[o].s);

	assert(t[o].maxf || (t[o].maxf == 0 && t[o].s == R - L + 1));

}

inline void pushdown(int o, int L, int R) {

	if (!t[o].add) return;

	int M = (L + R) >> 1;

	t[lc].sum += t[o].add * (M - L + 1), t[lc].add += t[o].add;

	t[lc].sumc += t[o].add * t[lc].s, t[lc].maxf && (t[lc].maxf += t[o].add);

	t[rc].sum += t[o].add * (R - M), t[rc].add += t[o].add;

	t[rc].sumc += t[o].add * t[rc].s, t[rc].maxf && (t[rc].maxf += t[o].add);

	t[o].add = 0;

}

inline void build(int o, int L, int R) {

	t[o].add = 0;

	if (L == R) {

		t[o].sum = a[pre[L]];

		t[o].maxf = std::min(0, a[pre[L]]);

		t[o].sumc = std::max(a[pre[L]], 0);

		t[o].s = a[pre[L]] >= 0;

		return;

	}

	int M = (L + R) >> 1;

	build(lc, L, M), build(rc, M + 1, R);

	pushup(o, L, R);

}

inline void qadd(int o, int L, int R, int l, int r, int k) {

	// dbg("qadd : o = %d, L = %d, R = %d, l = %d, r = %d, k = %d, t[o].maxf = %lld, t[o].sum = %lld, t[o].sumc = %lld, t[o].s = %d, t[o].add = %lld\n", o, L, R, l, r, k, t[o].maxf, t[o].sum, t[o].sumc, t[o].s, t[o].add);

	if (l <= L && R <= r && (!t[o].maxf || t[o].maxf < -k)) {

		t[o].sum += k * (ll)(R - L + 1);

		t[o].sumc += k * (ll)t[o].s;

		t[o].add += k;

		if (t[o].maxf) t[o].maxf += k;

		return;

	}

	if (L == R) {

		t[o].sum += k, t[o].add += k;

		t[o].sumc = std::max(0ll, t[o].sum);

		t[o].s = t[o].sum >= 0;

		t[o].maxf = std::min(0ll, t[o].sum);

		return;

	}

	int M = (L + R) >> 1;

	pushdown(o, L, R);

	if (l <= M) qadd(lc, L, M, l, r, k);

	if (r > M) qadd(rc, M + 1, R, l, r, k);

	pushup(o, L, R);

}

inline ll qsum(int o, int L, int R, int l, int r)  {

	// dbg("qsum : o = %d, L = %d, R = %d, l = %d, r = %d\n", o, L, R, l, r);

	if (l <= L && R <= r) return t[o].sumc * 2 - t[o].sum;

	int M = (L + R) >> 1;

	pushdown(o, L, R);

	if (r <= M) return qsum(lc, L, M, l, r);

	if (l > M) return qsum(rc, M + 1, R, l, r);

	return qsum(lc, L, M, l, r) + qsum(rc, M + 1, R, l, r);

}

inline void upd(int x, int y, int k) {

	while (top[x] != top[y]) {

		if (dep[top[x]] < dep[top[y]]) std::swap(x, y);

		qadd(1, 1, n, dfn[top[x]], dfn[x], k);

		x = f[top[x]];

	}

	if (dep[x] > dep[y]) std::swap(x, y);

	qadd(1, 1, n, dfn[x], dfn[y], k);

}

inline ll qry(int x, int y) {

	ll ans = 0;

	while (top[x] != top[y]) {

		if (dep[top[x]] < dep[top[y]]) std::swap(x, y);

		ans += qsum(1, 1, n, dfn[top[x]], dfn[x]);

		x = f[top[x]];

	}

	if (dep[x] > dep[y]) std::swap(x, y);

	return ans += qsum(1, 1, n, dfn[x], dfn[y]);

}

inline void dfs1(int x, int fa = 0) {

	dep[x] = dep[fa] + 1, f[x] = fa, siz[x] = 1;

	for fec(i, x, y) if (y != fa) dfs1(y, x), siz[x] += siz[y], siz[y] > siz[son[x]] && (son[x] = y);

}

inline void dfs2(int x, int pa) {

	// dbg("x = %d, pa = %d\n", x, pa);

	top[x] = pa, dfn[x] = ++dfc, pre[dfc] = x;

	if (!son[x]) return; dfs2(son[x], pa);

	for fec(i, x, y) if (y != son[x] && y != f[x]) dfs2(y, y);

}

inline void work() {

	dfs1(1), dfs2(1, 1), build(1, 1, n);

	while (m--) {

		int opt, x, y, z;

		read(opt), read(x), read(y);

		if (opt == 1) read(z), upd(x, y, z);

		else printf("%lld\n", qry(x, y));

	}

}

inline void init() {

	read(n), read(m);

	for (int i = 1; i <= n; ++i) read(a[i]);

	int x, y;

	for (int i = 1; i < n; ++i) read(x), read(y), adde(x, y);

}

int main() {

#ifdef hzhkk

	freopen("hkk.in", "r", stdin);

#endif

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}