```cpp
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
const int MAXN = 1e6 + 10;
const int INF = 0x3f;
LL n , m ;
LL head[MAXN] , to[MAXN] , ne[MAXN] , idx , a[MAXN] , cnt;
LL dep[MAXN] , top[MAXN] , son[MAXN] , fa[MAXN] , size[MAXN] , w[MAXN] , id[MAXN];
void edge_add(LL x, LL y)
{
to[++idx] = y , ne[idx] = head[x] , head[x] = idx;
}
struct node
{
LL l , r , sum , lazy;
}tr[MAXN];
void dfs1(LL u , LL f , LL d)
{
fa[u] = f , dep[u] = d , size[u] = 1;
for(LL i = head[u] ; i ; i = ne[i])
{
LL v = to[i];
if(v != f)
{
dfs1(v,u,d+1);
size[u] += size[v];
if(size[v] > size[ son[u] ])
son[u] = v;
}
}
}
void dfs2(LL u , LL f)
{
id[u] = ++cnt;
top[u] = f;
w[cnt] = a[u];
if(!son[u])
return ;
dfs2(son[u] , f);
for(LL i = head[u] ; i ; i = ne[i])
{
LL v = to[i];
if(v != fa[u] && v != son[u])
dfs2(v,v);
}
}
void down(LL s)
{
tr[s*2].lazy += tr[s].lazy;
tr[s*2+1].lazy += tr[s].lazy;
tr[s*2].sum = tr[s*2].sum + tr[s].lazy * (tr[s*2].r - tr[s*2].l + 1);
tr[s*2+1].sum = tr[s*2+1].sum + tr[s].lazy * (tr[s*2+1].r - tr[s*2+1].l + 1);
tr[s].lazy = 0;
}
void build(LL s , LL l , LL r )
{
tr[s].l = l , tr[s].r = r , tr[s].lazy = 0;
if(l == r)
{
tr[s].sum = w[l];
return ;
}
LL mid = (l + r) >> 1;
build(s*2 , l , mid);
build(s*2+1 , mid + 1 , r);
tr[s].sum = tr[s*2].sum + tr[s*2 + 1].sum;
}
void update(LL s , LL x, LL val)
{
if(tr[s].l == tr[s].r)
{
tr[s].sum += val;
return ;
}
if(tr[s].lazy)
down(s);
LL mid = (tr[s].l + tr[s].r) / 2;
if(mid >= x)
update(s*2 , x , val);
else
update(s*2+1, x ,val);
tr[s].sum = tr[s*2].sum + tr[s*2 + 1].sum;
}
LL find(LL s , LL l , LL r)
{
if(tr[s].l >= l && tr[s].r <= r)
return tr[s].sum;
if(tr[s].lazy)
down(s);
LL ans = 0;
LL mid = (tr[s].l + tr[s].r) / 2;
if(mid >= l)
ans += find(s*2 , l , r);
if(mid < r)
ans += find(s*2+1 , l , r);
return ans;
}
LL Query(LL s , LL l , LL r)
{
LL ans = 0;
while(top[l] != top[r])
{
if(dep[top[l]] < dep[top[r]])
swap(l,r);
ans += find(1 , id[top[l]] , id[l]);
l = fa[top[l]];
}
if(dep[l] > dep[r])
swap(l,r);
ans += find(1 , id[l] , id[r]);
return ans;
}
void tree_add(LL s , LL l , LL r, LL val)
{
if(tr[s].l >= l && tr[s].r <= r)
{
tr[s].sum =tr[s].sum + val* (tr[s].r - tr[s].l + 1);
tr[s].lazy += val;
return ;
}
if(tr[s].lazy)
down(s);
LL mid = (tr[s].l + tr[s].r) / 2;
if(mid >= l)
tree_add(s*2 , l , r, val);
if(mid < r)
tree_add(s * 2 + 1, l , r, val);
tr[s].sum = tr[s*2].sum + tr[s*2 + 1].sum;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n ; i++)
cin >> a[i];
for(LL i = 1,x,y ; i < n ; i++)
{
cin >> x >> y;
edge_add(x,y);
edge_add(y,x);
}
cnt = 0;
dfs1(1,0,1);
dfs2(1,1);
build(1,1,n);
while(m--)
{
LL x,y,z;
cin >> z;
if(z == 1)
{
cin >> x >> y;
update(1 , id[x] ,y);
}
if(z == 2)
{
cin >> x >> y;
tree_add(1 , id[x] , id[x] + size[x] - 1 ,y);
}
if(z == 3)
{
cin >> x;
cout << Query(1,1,x) << endl;
}
}
return 0;
}
```
by 蔡竣凯 @ 2022-05-03 10:12:27
已发现是`long long int`的锅，此贴完结
by cqbzhsh @ 2022-05-03 10:19:45