给你我的看看
```cpp
#include<cstdio>
#include<vector>
using namespace std;
const long long N=1e5+5;
long long ori[N],dep[N],fa[N],son[N],a[N],siz[N],top[N],id[N],w[N<<2],lzy[N<<2],dfscnt=0;
vector<long long> G[N];
inline bool inRange(long long L,long long R,long long l,long long r){return l<=L&&R<=r;}
inline bool outofRange(long long L,long long R,long long l,long long r){return R<l||r<L;}
inline void pushup(long long u){w[u]=w[2*u]+w[2*u+1];}
void maketag(long long u,long long len,long long val)
{
lzy[u]+=val;
w[u]+=len*val;
}
void pushdown(long long u,long long L,long long R)
{
long long mid=(L+R)/2;
maketag(2*u,mid-L+1,lzy[u]);
maketag(2*u+1,R-mid,lzy[u]);
lzy[u]=0;
}
void build(long long u,long long L,long long R)
{
lzy[u]=0;
if(L==R)
{
w[u]=a[L];
return;
}
long long mid=(L+R)/2;
build(2*u,L,mid);
build(2*u+1,mid+1,R);
pushup(u);
}
long long query(long long u,long long L,long long R,long long l,long long r)
{
if(inRange(L,R,l,r)) return w[u];
else if(!outofRange(L,R,l,r))
{
pushdown(u,L,R);
long long mid=(L+R)/2;
return query(2*u,L,mid,l,r)+query(2*u+1,mid+1,R,l,r);
}
else return 0;
}
void update(long long u,long long L,long long R,long long l,long long r,long long val)
{
if(inRange(L,R,l,r)) maketag(u,R-L+1,val);
else if(!outofRange(L,R,l,r))
{
pushdown(u,L,R);
long long mid=(L+R)/2;
update(2*u,L,mid,l,r,val);
update(2*u+1,mid+1,R,l,r,val);
pushup(u);
}
else return;
}
void dfs1(long long u,long long f)
{
siz[u]=1;
dep[u]=dep[f]+1;
fa[u]=f;
vector<long long>::iterator it=G[u].begin();
for(;it!=G[u].end();it++)
{
if(*it==f) continue;
dfs1(*it,u);
siz[u]+=siz[*it];
if(!son[u]||siz[son[u]]<siz[*it]) son[u]=*it;
}
return;
}
void dfs2(long long u,long long topu)
{
id[u]=++dfscnt;
a[dfscnt]=ori[u];
top[u]=topu;
if(!son[u]) return;
dfs2(son[u],topu);
vector<long long>::iterator it=G[u].begin();
for(;it!=G[u].end();it++)
{
if(*it==fa[u]||*it==son[u]) continue;
dfs2(*it,*it);
}
}
void singlep_update(long long x,long long val,const long long n){update(1,1,n,id[x],id[x],val);}
void update_tree(long long x,long long val,const long long n){update(1,1,n,id[x],id[x]+siz[x]-1,val);}
void swap(long long &x,long long &y){x^=y;y^=x;x^=y;}
long long query_range(long long u,long long v,const long long n)
{
long long ans=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
ans+=query(1,1,n,id[top[u]],id[u]);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
ans+=query(1,1,n,id[u],id[v]);
return ans;
}
int main()
{
long long n,m;
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++) scanf("%lld",&ori[i]);
for(long long i=1;i<n;i++)
{
long long curfrom,curto;
scanf("%lld%lld",&curfrom,&curto);
G[curfrom].push_back(curto);
G[curto].push_back(curfrom);
}
dfs1(1,0);
dfs2(1,1);
build(1,1,n);
while(m--)
{
long long op;
scanf("%lld",&op);
if(op==1)
{
long long x,a;
scanf("%lld%lld",&x,&a);
singlep_update(x,a,n);
// for(long long i=1;i<=n;i++) prlong longf("%d ",query(1,1,n,id[i],id[i]));
// prlong longf("\n");
}
else if(op==2)
{
long long x,a;
scanf("%lld%lld",&x,&a);
update_tree(x,a,n);
// for(long long i=1;i<=n;i++) prlong longf("%d ",query(1,1,n,id[i],id[i]));
// prlong longf("\n");
}
else if(op==3)
{
long long x;
scanf("%lld",&x);
printf("%lld\n",query_range(1,x,n));
}
}
return 0;
}
```
by Lizichen_licis @ 2024-03-14 21:47:43