```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
const int N = 100005;
int bg[N], ed[N], tim;
int a[N];
int n, m;
int head[N], ver[N*2], nxt[N*2], cnt;
ll sum[N*4], f[N*4];
int fa[N], son[N], siz[N], top[N], dep[N];
void add(int p, int L, int R, int val) {
sum[p] += 1ll * val * (R - L + 1);
f[p] += val;
}
void pushdown(int p, int L, int R) {
if (L == R) return;
int mid = L + R >> 1, ls = p << 1, rs = ls | 1;
add(ls, L, mid, f[p]), add(rs, mid + 1, R, f[p]);
f[p] = 0;
}
void modify(int p, int L, int R, int l, int r, int val) {
if (l <= L && R <= r) {
add(p, L, R, val);
return;
}
pushdown(p, L, R);
int mid = L + R >> 1, ls = p << 1, rs = ls | 1;
if (l <= mid) modify(ls, L, mid, l, r, val);
if (r > mid) modify(rs, mid + 1, R, l, r, val);
sum[p] = sum[ls] + sum[rs];
}
ll query(int p, int L, int R, int l, int r) {
if (l <= L && R <= r) return sum[p];
pushdown(p, L, R);
int mid = L + R >> 1, ls = p << 1, rs = ls | 1;
return (l <= mid ? query(ls, L, mid, l, r) : 0) + (r > mid ? query(rs, mid + 1, R, l, r) : 0);
}
void modify(int l, int r, int val) {
modify(1, 1, n, l, r, val);
}
ll query(int l, int r) {
return query(1, 1, n, l, r);
}
void dfs1(int u) {
siz[u] = 1;
son[u] = -1;
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (dep[v]) continue;
dep[v] = dep[u] + 1;
fa[v] = u;
dfs1(v);
siz[u] += siz[v];
if (son[u] == -1 || siz[v] > siz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int t) {
top[u] = t;
bg[u] = ++tim;
if (son[u] == -1) {
ed[u] = tim;
return;
}
dfs2(son[u], t);
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v);
}
ed[u] = tim;
}
void addEdge(int u, int v) {
ver[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}
ll queryLink(int l, int r) {
ll res = 0;
while (top[l] ^ top[r]) {
if (dep[top[l]] < dep[top[r]]) swap(l, r);
res += query(bg[top[l]], bg[l]);
l = fa[top[l]];
}
if (bg[l] > bg[r]) swap(l, r);
res += query(bg[l], bg[r]);
return res;
}
il int qrint() {
int s = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
s = (s << 1) + (s << 3) + (ch ^ 48);
ch = getchar();
}
return s * f;
}
int main() {
n = qrint(), m = qrint();
for (int i = 1; i <= n; ++i) a[i] = qrint();
for (int i = 1; i < n; ++i) {
int u = qrint(), v = qrint();
addEdge(u, v), addEdge(v, u);
}
dep[1] = 1;
dfs1(1);
dfs2(1, 1);
for (int i = 1; i <= n; ++i) modify(bg[i], bg[i], a[i]);
while (m--) {
int op = qrint();
if (op == 1) {
int u = qrint(), w = qrint();
modify(bg[u], bg[u], w);
}
if (op == 2) {
int u = qrint(), w = qrint();
modify(bg[u], ed[u], w);
}
if (op == 3) {
int u = qrint();
printf("%lld\n", queryLink(u, 1));
}
}
return 0;
}
```
代码贴二楼
by Kobe303 @ 2022-02-18 20:52:35
为什么全开 ```long long``` 就行了呀
我不理解（
by Kobe303 @ 2022-02-18 20:59:51
有大佬可以指出我二楼贴的代码哪里会爆 ```int``` 吗qwq
by Kobe303 @ 2022-02-18 21:00:34
@[Kobe303](/user/292300) 转成重剖序之后 $a_i$ 没有映射过来。
by BqtMtsZDnlpsT @ 2022-02-18 21:01:08
啊，看错了/kk
by BqtMtsZDnlpsT @ 2022-02-18 21:01:49
@[Freedom_King](/user/185864) ?
by Kobe303 @ 2022-02-18 21:01:57
```cpp
void add(int p, int L, int R, int val) {
sum[p] += 1ll * val * (R - L + 1);
f[p] += val;
}
```
by BqtMtsZDnlpsT @ 2022-02-18 21:05:17
@[Kobe303](/user/292300) val 是 ll 的吧，加 lazy tag 的时候要炸的
by BqtMtsZDnlpsT @ 2022-02-18 21:05:57
@[Freedom_King](/user/185864) 哎你说的是上面一行还是下面一行？
by Kobe303 @ 2022-02-18 21:06:50
@[Kobe303](/user/292300)
```cpp
void add(int p, int L, int R, int val)
```
by BqtMtsZDnlpsT @ 2022-02-18 21:07:25