```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug cout<<"Here?"<<endl;
const int maxn=300010;
int n,m,tot=0,h[maxn],val[maxn],lazytag[maxn],tree[maxn*3],sum[maxn],size[maxn],cnt[maxn];
int id[maxn],dep[maxn],fa[maxn],top[maxn],big[maxn];
struct Edge{
int to;
int next;
}e[maxn];
void add(int u,int v)
{
e[++tot].to=v;
e[tot].next=h[u];
h[u]=tot;
}
void build(int k,int l,int r)
{
if(l==r)
{
tree[k]=cnt[l];
return ;
}
int mid=(l+r)>>1;
build(k>>1,l,mid);
build(k>>1|1,mid+1,r);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
void dfs1(int now,int f)
{
dep[now]=dep[f]+1;
size[now]=1;
fa[now]=f;
for(int i=h[now];i;i=e[i].next)
{
int to=e[i].to;
if(to==f) continue;
dfs1(to,now);
size[now]+=size[to];
if(big[now]==-1||size[to]>size[big[now]]) big[now]=to;
}
return ;
}
int num=0;
void dfs2(int now,int tp)
{
top[now]=tp;
id[now]=++num;
if(big[now]==-1) return ;
// cout<<now<<"de"<<endl;
cnt[num]=val[now];
if(big[now]) dfs2(big[now],tp);
for(int i=h[now],to=e[i].to;i;i=e[i].next)
{
if(to==fa[now]) continue;
if(to==big[now]) continue;
dfs2(to,to);
}
}
void pushdown(int k,int len)
{
lazytag[k<<1]+=lazytag[k];
lazytag[k<<1|1]+=lazytag[k];
sum[k<<1]+=lazytag[k]*(len-(len>>1));
sum[k<<1|1]+=lazytag[k]*(len>>1);
lazytag[k]=0;
}
void update(int k,int l,int r,int x,int y,int p)
{
if(x<=l&&r<=y)
{
lazytag[k]+=p;
sum[k]+=(y-x+1)*p;
return ;
}
if(lazytag[k]) pushdown(k,r-l+1);
int mid=(l+r)>>1;
if(x<=mid) update(k<<1,l,mid,x,y,p);
if(y>mid) update(k<<1|1,mid+1,r,x,y,p);
sum[k]=sum[k<<1]+sum[k<<1|1];
}
int res=0;
void find(int k,int l,int r,int x,int y)
{
if(l>=x&&r<=y)
{
res+=sum[k];
return ;
}else{
int mid=(l+r)>>1;
//debug
// if(lazytag[k]) pushdown(k,r-l+1); //加上这行就无法运行了/px
if(x<=mid) find(k<<1,l,mid,x,y);
if(y>mid) find(k<<1|1,mid+1,r,x,y);
}
// return res;
}
int query(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
//debug
find(1,1,n,id[top[x]],id[x]);
ans+=res;
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res=0;
find(1,1,n,id[x],id[y]);
// cout<<"qqqq"<<1<<' '<<n<<' '<<id[2]<<' '<<id[3]<<endl;
ans+=res;
return ans;
}
signed main()
{
memset(big,-1,sizeof big);
int xx,yy;
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%lld",&val[i]);
for(int i=1;i<n;i++) scanf("%lld%lld",&xx,&yy),add(xx,yy),add(yy,xx);
dfs1(1,0);
// for(int i=1;i<=n;i++)
// {
// cout<<big[i]<<'w'<<endl;
// }
dfs2(1,1);
build(1,1,n);
while(m--)
{
int opt;
cin>>opt;
if(opt==1)
{
scanf("%lld%lld",&xx,&yy);
update(1,1,n,id[xx],id[xx],yy);
}
if(opt==2)
{
scanf("%lld%lld",&xx,&yy);
update(1,1,n,id[xx],id[xx]+size[id[xx]]-1,yy);
}
if(opt==3)
{
scanf("%lld",&xx);
cout<<query(1,xx)<<endl;
}
}
// for(int i=1;i<=n;i++) cout<<id[i]<<endl;
return 0;
}
// id x
```
by Yukinoshita_Yukino @ 2022-01-28 08:10:51
~~find 函数开成 int 的不好吗拿全局变量存答案还容易清零不彻底~~
by StarLbright40 @ 2022-01-28 08:23:30
@[Maksur](/user/173323) 不是你这个res为啥不在每次find后都清零呢？不清零你第二次find之后res的值就是前两次的总和，然后你的ans就会再把第一次的累加一遍
by __zzy__ @ 2022-01-28 09:03:08
还有你的dfs2写的什么鬼....没有重儿子的叶节点也要先 ```cnt[num]=val[now]```再返回啊，下面的那个for循环令我懵逼，你的to初始化一次之后再也没变过，循环了个啥
by __zzy__ @ 2022-01-28 09:04:48
update里面也是，当前被覆盖的区间是 $[l,r]$ ,但是你增加的值是整个修改区间的长度*增加的值```p```
by __zzy__ @ 2022-01-28 09:06:26
还有下面对子树进行修改的时候，$x$的子树大小就是 $size[x]$ 啊，你重新标号之后又没改size数组，怎么能用第二遍的标号去调用
by __zzy__ @ 2022-01-28 09:08:38
除了我说的这几个还有错，样例仍然没过，我再改改。
建议重新学习树剖
by __zzy__ @ 2022-01-28 09:09:36
@[__zzy__](/user/478552) wssb,谢谢大佬/bx
by Yukinoshita_Yukino @ 2022-01-28 09:11:22
@[Maksur](/user/173323) CaO你厉害啊，线段树建树错了....我拿我AC代码对了半天差点没看出来.....
建树的那个是 ```build(k<<1,l,mid),build(k<<1|1,mid+1,r)```
你写了个
```build(k>>1,l,mid),build(k>>1|1,mid+1,r)```
by __zzy__ @ 2022-01-28 09:27:24
恭喜0号节点荣获MVP
by __zzy__ @ 2022-01-28 09:27:46