题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=4127
题解
首先区间绝对值和可以转化为 (2) 倍的区间正数和 (-) 区间和。于是问题就转化为区间正数和。
因为每一次增加的量 (d geq 0)，所以每一个数只会被从负数变成正数一次。也就是说，从负变正的操作最多出现 (n) 次。
于是我们考虑在线段树上对于从负数变成正数的操作暴力修改。
如何判断一个区间内有负数变成正数的操作呢。令 (c) 表示这个区间的最大负数。于是如果 (-k leq c leq 0) 那么说明区间有数从负变正。
那么每一次从负变正都会走 (log n) 个线段树节点，于是所有数从负变正而来的总时间为 (O(nlog n))。
其余的修改的复杂度为 (O(qlog 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
", 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
", 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
", 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
", 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
", 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;
}