这个题感觉很厉害的样子。。
首先我们注意到一点：每次加的 $d$ 都是非负的。
那么就说明一个数只可能从负数变成非负数并且只会变一次。
所以我们就可以暴力地去改变一个数的正负情况。
然后我们就可以用树链剖分，维护一下区间的最大负数和负数的个数就可以了。
时间复杂度 $O(n\log^2 n)$，空间复杂度 $O(n)$。
#include <cstdio>
typedef long long LL;
#define N 262144 + 5
#define INF 1234567890987654321LL int n, m, tot, cnt, A[N], Head[N], Root[N], Fa[N], Ad[N], Pos[N], Num[N], Dfn[N], Len[N], Size[N], Son[N], q[N]; struct Edge
{
int next, node;
}E[N]; struct Segment_Tree
{
int l, r, neg_cnt;
LL sum, delta, neg_Max;
}h[N]; inline void addedge(int u, int v)
{
E[++ tot].next = Head[u], Head[u] = tot;
E[tot].node = v;
E[++ tot].next = Head[v], Head[v] = tot;
E[tot].node = u;
} inline LL Abs(LL x)
{
return x > ? x : -x;
} inline void dfs(int z)
{
Size[z] = ;
for (int i = Head[z]; i; i = E[i].next)
{
int d = E[i].node;
if (d == Fa[z]) continue ;
Fa[d] = z;
dfs(d);
Size[z] += Size[d];
}
for (int i = Head[z]; i; i = E[i].next)
{
int d = E[i].node;
if (d == Fa[z]) continue ;
if (!Son[z] || Size[d] > Size[Son[z]])
Son[z] = d;
}
} inline void update(int x)
{
h[x].sum = h[h[x].l].sum + h[h[x].r].sum;
h[x].neg_Max = h[h[x].l].neg_Max > h[h[x].r].neg_Max ? h[h[x].l].neg_Max : h[h[x].r].neg_Max;
h[x].neg_cnt = h[h[x].l].neg_cnt + h[h[x].r].neg_cnt;
} inline void Build(int &x, int l, int r)
{
if (!x) x = ++ tot;
if (l == r)
{
h[x].sum = Abs(A[q[l]]);
if (A[q[l]] < ) h[x].neg_Max = A[q[l]], h[x].neg_cnt = ;
else h[x].neg_Max = -INF;
return ;
}
int mid = l + r >> ;
Build(h[x].l, l, mid);
Build(h[x].r, mid + , r);
update(x);
} inline void apply(int x, int l, int r, LL d)
{
h[x].sum += d * (r - l + - h[x].neg_cnt * );
h[x].delta += d;
h[x].neg_Max += d;
} inline void push(int x, int l, int r)
{
if (h[x].delta)
{
int mid = l + r >> ;
apply(h[x].l, l, mid, h[x].delta);
apply(h[x].r, mid + , r, h[x].delta);
h[x].delta = ;
}
} inline void Point_Modify(int x, int l, int r, LL d)
{
if (l == r)
{
h[x].sum = -h[x].sum;
h[x].neg_Max = -INF;
h[x].neg_cnt = ;
return ;
}
int mid = l + r >> ;
push(x, l, r);
if (h[h[x].l].neg_Max > h[h[x].r].neg_Max)
Point_Modify(h[x].l, l, mid, d);
else Point_Modify(h[x].r, mid + , r, d);
update(x);
} inline void Modify(int x, int l, int r, int s, int t, LL d)
{
if (l == s && r == t)
{
while (h[x].neg_Max >= -d)
Point_Modify(x, l, r, d);
apply(x, l, r, d);
return ;
}
push(x, l, r);
int mid = l + r >> ;
if (t <= mid) Modify(h[x].l, l, mid, s, t, d);
else if (s > mid) Modify(h[x].r, mid + , r, s, t, d);
else Modify(h[x].l, l, mid, s, mid, d), Modify(h[x].r, mid + , r, mid + , t, d);
update(x);
} inline LL Query(int x, int l, int r, int s, int t)
{
if (l == s && r == t) return h[x].sum;
push(x, l, r);
int mid = l + r >> ;
if (t <= mid) return Query(h[x].l, l, mid, s, t);
else if (s > mid) return Query(h[x].r, mid + , r, s, t);
else return Query(h[x].l, l, mid, s, mid) + Query(h[x].r, mid + , r, mid + , t);
} inline void Prepare()
{
tot = ;
for (int i = ; i <= n; i ++)
{
if (Ad[i]) continue ;
Dfn[i] = Dfn[Fa[i]] + ;
q[] = ;
cnt ++;
for (int x = i; x; x = Son[x])
{
Ad[x] = i, Pos[x] = ++ Len[cnt];
Num[x] = cnt, Dfn[x] = Dfn[i];
q[++ q[]] = x;
}
Build(Root[cnt], , Len[cnt]);
}
} int main()
{
#ifndef ONLINE_JUDGE
freopen("4127.in", "r", stdin);
freopen("4127.out", "w", stdout);
#endif scanf("%d%d", &n, &m);
for (int i = ; i <= n; i ++)
scanf("%d", A + i);
for (int i = , u, v; i < n; i ++)
{
scanf("%d%d", &u, &v);
addedge(u, v);
}
dfs();
Prepare();
for (int op, u, v; m; m --)
{
scanf("%d", &op);
if (op == )
{
LL d;
scanf("%d%d%lld", &u, &v, &d);
if (Dfn[u] < Dfn[v]) u = u - v, v = u + v, u = v - u;
for (; Dfn[u] > Dfn[v]; u = Fa[Ad[u]])
Modify(Root[Num[u]], , Len[Num[u]], , Pos[u], d);
for (; Ad[u] != Ad[v]; u = Fa[Ad[u]], v = Fa[Ad[v]])
{
Modify(Root[Num[u]], , Len[Num[u]], , Pos[u], d);
Modify(Root[Num[v]], , Len[Num[v]], , Pos[v], d);
}
if (Pos[u] > Pos[v]) u = u - v, v = u + v, u = v - u;
Modify(Root[Num[u]], , Len[Num[u]], Pos[u], Pos[v], d);
}
else
{
scanf("%d%d", &u, &v);
LL ans = ;
if (Dfn[u] < Dfn[v]) u = u - v, v = u + v, u = v - u;
for (; Dfn[u] > Dfn[v]; u = Fa[Ad[u]])
ans += Query(Root[Num[u]], , Len[Num[u]], , Pos[u]);
for (; Ad[u] != Ad[v]; u = Fa[Ad[u]], v = Fa[Ad[v]])
{
ans += Query(Root[Num[u]], , Len[Num[u]], , Pos[u]);
ans += Query(Root[Num[v]], , Len[Num[v]], , Pos[v]);
}
if (Pos[u] > Pos[v]) u = u - v, v = u + v, u = v - u;
ans += Query(Root[Num[u]], , Len[Num[u]], Pos[u], Pos[v]);
printf("%lld\n", ans);
}
} #ifndef ONLINE_JUDGE
fclose(stdin);
fclose(stdout);
#endif
return ;
}
4127_Gromah