```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, m, root, dep[N], l[N], dfn[N];
int fa[N], size[N], son[N], top[N];
long long val[N], ans[N];
struct node
{
int next, to, w;
} Node[N << 1];//链式前向星存储
int R, cnt, head[N], id, num;
typedef struct NODE
{
int l, r;
long long val, lazy;
} TREE;
TREE tree[N * 4 + 5];//线段树
void build(int id, int le, int ri)//建树
{
tree[id].l = le;
tree[id].r = ri;
if (le == ri)
{
tree[id].val = val[dfn[le]];
tree[id].lazy = 0;
return;
}
int mid = (le + ri) >> 1;
build(id * 2, le, mid);
build(id * 2 + 1, mid + 1, ri);
tree[id].val = tree[id * 2].val + tree[id * 2 + 1].val;
tree[id].lazy = 0;
}
void down(int id)//下放懒惰标记
{
tree[id * 2].val += tree[id].lazy * (tree[id * 2].r - tree[id * 2].l + 1);
tree[id * 2].lazy += tree[id].lazy;
tree[id * 2 + 1].val += tree[id].lazy * (tree[id * 2 + 1].r - tree[id * 2 + 1].l + 1);
tree[id * 2 + 1].lazy += tree[id].lazy;
tree[id].lazy = 0;
}
void add_unsingle(int id, int l, int r, long long val)//区间修改
{
if (tree[id].l >= l && tree[id].r <= r)
{
tree[id].val += val * (tree[id].r - tree[id].l + 1);
tree[id].lazy += val;
return;
}
if (tree[id].lazy)
down(id);
int mid = (tree[id].l + tree[id].r) >> 1;
if (l <= mid)
add_unsingle(id * 2, l, r, val);
else
add_unsingle(id * 2 + 1, l, r, val);
tree[id].val = tree[id * 2].val + tree[id * 2 + 1].val;
}
void add_single(int id, int goal, long long val)//单点修改
{
if (tree[id].l == goal && tree[id].r == goal)
{
tree[id].val += val;
return;
}
if (tree[id].lazy)
down(id);
int mid = (tree[id].l + tree[id].r) >> 1;
if (goal <= mid)
add_single(id * 2, goal, val);
else
add_single(id * 2 + 1, goal, val);
tree[id].val = tree[id * 2].val + tree[id * 2 + 1].val;
}
long long quessum(int id, int l, int r)//区间和查询
{
if (tree[id].l >= l && tree[id].r <= r)
return tree[id].val;
int mid = (tree[id].l + tree[id].r) >> 1;
long long ans = 0;
if (tree[id].lazy)
down(id);
if (l <= mid)
ans = quessum(id * 2, l, r);
if (r > mid)
ans += quessum(id * 2 + 1, l, r);
return ans;
}
void Add(int x, int y, int v)//链式前向星加边
{
Node[++cnt].next = head[x];
Node[cnt].to = y;
Node[cnt].w = v;
head[x] = cnt;
}
void light_chain(int now)//dfs1(前准备工作)
{
size[now] = 1;
dep[now] = dep[fa[now]] + 1;
int i;
for (i = head[now]; i; i = Node[i].next)
{
if (Node[i].to == fa[now])
continue;
fa[Node[i].to] = now;
light_chain(Node[i].to);
size[now] += size[Node[i].to];
if (size[Node[i].to] > size[son[now]])
son[now] = Node[i].to;
}
}
void subd(int now, int tp)//dfs2(剖分)
{
top[now] = tp;
l[now] = ++id;
dfn[id] = now;
int i;
if (son[now])
subd(son[now], tp);
for (i = head[now]; i; i = Node[i].next)
{
if (Node[i].to != fa[now] && Node[i].to != son[now])
subd(Node[i].to, Node[i].to);
}
}
long long qsum(int x, int y)//求答案
{
long long res = 0;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
swap(x, y);
res += quessum(1, l[top[x]], l[x]);
x = fa[top[x]];
}
if (dep[x] > dep[y])
swap(x, y);
return res += quessum(1, l[x], l[y]);
}
int main()
{
int n, m, i, u, v, x, y, num = 0, s;
scanf("%d", &n);
scanf("%d", &m);
for (i = 1; i <= n; i++)
scanf("%lld", &val[i]);
for (i = 1; i < n; i++)
{
scanf("%d %d", &u, &v);
Add(u, v, 0);
Add(v, u, 0);
}
light_chain(1);
subd(1, 1);
build(1, 1, n);
for (i = 1; i <= m; i++)
{
scanf("%d %d", &s, &x);
if (s == 1)
scanf("%d", &y), add_single(1, l[x], y);
if (s == 2)
scanf("%d", &y), add_unsingle(1, l[x], l[x] + size[x] - 1, y);
if (s == 3)
ans[++num] = qsum(1, x);
}
for (i = 1; i <= num; i++)
printf("%lld\n", ans[i]);
return 0;
}
```
by Harry_Hedwig @ 2022-05-02 20:54:04
可能是很 zz 的错误,但是看半天是真的没看出来/kk
by Harry_Hedwig @ 2022-05-02 21:01:09
@[Harry_Hedwig](/user/465692)
```cpp
void add_unsingle(int id, int l, int r, long long val)//区间修改
{
if (tree[id].l >= l && tree[id].r <= r)
{
tree[id].val += val * (tree[id].r - tree[id].l + 1);
tree[id].lazy += val;
return;
}
if (tree[id].lazy)
down(id);
int mid = (tree[id].l + tree[id].r) >> 1;
if (l <= mid)
add_unsingle(id * 2, l, r, val);
if(mid < r)//把这里改了就好了
add_unsingle(id * 2 + 1, l, r, val);
tree[id].val = tree[id * 2].val + tree[id * 2 + 1].val;
}
by E_firework @ 2022-05-02 21:23:36
真就是zz错误
by E_firework @ 2022-05-02 21:24:04
@[Harry_Hedwig](/user/465692) 感觉区间修改可能写假了?
```cpp
if (l <= mid)
add_unsingle(id * 2, l, r, val);
else //此处改为 if (r > mid)
add_unsingle(id * 2 + 1, l, r, val);
```
by XeCtera @ 2022-05-02 21:25:06
@[E_firework](/user/488539) @[IcMtr](/user/38785) 谢谢谢谢就是这的问题真的十分感谢
by Harry_Hedwig @ 2022-05-02 21:29:50
顺便捞一下[我的](https://www.luogu.com.cn/discuss/435377)
by cqbzhsh @ 2022-05-03 08:30:04