傳送門:點選打開連結
題意:
有一棵點數為 N 的樹,以點 1 為根,且樹點有邊權。有 M 個操作,分為三種:
操作 1 :把某個節點 x 的點權增加 a 。
操作 2 :把某個節點 x 為根的子樹中所有點的點權都增加 a 。
操作 3 :詢問某個節點 x 到根的路徑中所有點的點權和。
資料範圍:
N,M<=100000 ,且所有輸入資料的絕對值都不會超過 10^6 。
DFS序的闆子題,網上部落格很多,都比較好了解。
代碼實作的時候用線段樹來二分排dfs序。要注意的是,dfs序in和out要同時更新,注意正負。
用的是樸素做法,據說可以樹鍊剖分,可我不會啊。才學就打一個樸素版吧。
//3.11:我來補代碼了:樹鍊剖分:點選打開連結
代碼
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+2;
int n,m,root=1,cnt,tot,ini[N],num;
int in[N],out[N],df[600010];
int to[N<<1],next[N<<1],head[N<<1];
struct node{
int l,r;
int fu,zh;//zh->zheng_fu->fu
ll sum,add;
}t[2400010];
inline void link(int u,int v){
++tot;
next[tot]=head[u];
head[u]=tot;
to[tot]=v;
}
inline void pushdown(int x){
if(t[x].add==0) return;
t[x<<1].sum+=1ll*(t[x<<1].zh-t[x<<1].fu)*t[x].add;
t[x<<1|1].sum+=1ll*(t[x<<1|1].zh-t[x<<1|1].fu)*t[x].add;
t[x<<1].add+=t[x].add;
t[x<<1|1].add+=t[x].add;
t[x].add=0;
}
inline void maintain(int x){
t[x].sum=t[x<<1].sum+t[x<<1|1].sum;
}
inline void dfs(int fa,int k)
{
df[++cnt]=k;in[k]=cnt;
for(int i=head[k];i;i=next[i]){
if(to[i]!=fa)
dfs(k,to[i]);
}
df[++cnt]=-k;out[k]=cnt;
}
inline void build(int k,int l,int r){
t[k].l=l,t[k].r=r;t[k].sum=t[k].add=0;
if(l==r){
if(df[l]>0)
t[k].sum=(ll)ini[df[l]],t[k].zh++;
else t[k].sum=-(ll)ini[-df[l]],t[k].fu++;
}else{
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
maintain(k);
t[k].zh=t[k<<1].zh+t[k<<1|1].zh;
t[k].fu=t[k<<1].fu+t[k<<1|1].fu;
}
}
inline void ad(int k,int L,int R,ll addv)
{
if(t[k].l>=L && t[k].r<=R){
t[k].sum+=1ll*(t[k].zh-t[k].fu)*addv;
t[k].add+=addv;
}else{
pushdown(k);
int mid=(t[k].l+t[k].r)>>1;
if(R<=mid) ad(k<<1,L,R,addv);
else if(L>mid) ad(k<<1|1,L,R,addv);
else {
ad(k<<1,L,mid,addv);
ad(k<<1|1,mid+1,R,addv);
}
maintain(k);
}
}
inline ll query(int k,int L,int R)
{
if(t[k].l>=L && t[k].r<=R)
return t[k].sum;
int mid=(t[k].l+t[k].r)>>1;pushdown(k);
if(R<=mid) return query(k<<1,L,R);
else if(L>mid)
return query(k<<1|1,L,R);
else return
query(k<<1,L,mid) + query(k<<1|1,mid+1,R);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&ini[i]);
for(int x,y,i=1;i<n;i++){
scanf("%d%d",&x,&y);
link(x,y);
link(y,x);
}
dfs(0,root);
build(root,1,cnt);
while(m--){
int op,x,addx;
scanf("%d",&op);
if(op==1){
scanf("%d%d",&x,&addx);
ad(root,in[x],in[x],(ll)addx);
ad(root,out[x],out[x],(ll)addx);
}else if(op==2){
scanf("%d%d",&x,&addx);
int j=out[x];
ad(root,in[x],out[x],(ll)addx);
}else{
scanf("%d",&x);
printf("%lld\n",query(root,1,in[x]));
}
}
return 0;
}