传送门
解题思路
好板子啊。
要不是是个省选题
我才不写博客呢。
树剖完了，就是单点修改+区间修改+区间求和。
线段树维护即可。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100005;
long long d[maxn*4],lazy[maxn*4];
int n,m,p[maxn],cnt,siz[maxn],fa[maxn],son[maxn],id[maxn],tp[maxn],a[maxn],dfn[maxn],times;
struct node{
int v,next;
}e[maxn*2];
void insert(int u,int v){
cnt++;
e[cnt].v=v;
e[cnt].next=p[u];
p[u]=cnt;
}
void dfs1(int u,int f){
siz[u]=1;
fa[u]=f;
for(int i=p[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(v==f) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int top){
dfn[u]=++times;
id[times]=u;
tp[u]=top;
if(son[u]) dfs2(son[u],top);
for(int i=p[u];i!=-1;i=e[i].next){
int v=e[i].v;
if(v==son[u]||v==fa[u]) continue;
dfs2(v,v);
}
}
void pushdown(int id,int l,int r){
if(lazy[id]){
int mid=(l+r)/2;
lazy[id*2]+=lazy[id];
lazy[id*2+1]+=lazy[id];
d[id*2]+=1ll*(mid-l+1)*lazy[id];
d[id*2+1]+=1ll*(r-mid)*lazy[id];
lazy[id]=0;
}
}
void pushup(int id){
d[id]=d[id*2]+d[id*2+1];
}
void update(int id,int l,int r,int x,int y,long long v){
if(x>y) return;
if(x<=l&&r<=y){
d[id]+=v*(r-l+1);
lazy[id]+=v;
return;
}
int mid=(l+r)/2;
pushdown(id,l,r);
if(x<=mid) update(id*2,l,mid,x,y,v);
if(y>mid) update(id*2+1,mid+1,r,x,y,v);
pushup(id);
}
long long query(int id,int l,int r,int x,int y){
if(x>y) return 0;
if(x<=l&&r<=y){
return d[id];
}
pushdown(id,l,r);
int mid=(l+r)/2;
long long res=0;
if(x<=mid) res+=query(id*2,l,mid,x,y);
if(y>mid) res+=query(id*2+1,mid+1,r,x,y);
return res;
}
int main(){
ios::sync_with_stdio(false);
memset(p,-1,sizeof(p));
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
insert(u,v);
insert(v,u);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;i++) update(1,1,n,dfn[i],dfn[i],a[i]);
for(int i=1;i<=m;i++){
int op;
cin>>op;
if(op==1){
int u,x;
cin>>u>>x;
update(1,1,n,dfn[u],dfn[u],x);
continue;
}
if(op==2){
int u,x;
cin>>u>>x;
update(1,1,n,dfn[u],dfn[u]+siz[u]-1,x);
continue;
}
if(op==3){
int x;
long long ans=0;
cin>>x;
while(x!=0){
ans+=query(1,1,n,dfn[tp[x]],dfn[x]);
x=fa[tp[x]];
}
cout<<ans<<endl;
}
}
return 0;
}