【题目描述】

有一棵点数为N的树，以点1为根，且树点有边权。然后有M个操作，分为三种：

操作1：把某个节点x的点权增加a。

操作2：把某个节点x为根的子树中所有点的点权都增加a。

操作3：询问某个节点x到根的路径中所有点的点权和。

【输入格式】

第一行两个整数N,M，表示点数和操作数。

接下来一行N个整数，表示树中节点的初始权值。

接下来N-1行每行两个正整数fr,to，表示该树中存在一条边(fr,to)。

再接下来M行，每行分别表示一次操作。其中第一个数表示该操作的种类（1~3），之后接这个操作的参数（x或者x a）。

【输出格式】

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

【样例输入】

5 5

1 2 3 4 5

1 2

1 4

2 3

2 5

3 3

1 2 1

3 5

2 1 2

3 3

【样例输出】

6

9

13

【提示】

对于30%的数据，N,M<=1000

对于50%的数据，N,M<=100000且数据随机。

对于100%的数据，N,M<=100000，且所有输入数据的绝对值都不会超过10^6。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 using namespace std; 10 typedef long long LL; 11 const LL maxn=100010; 12 inline LL read(){ 13 LL x=0,f=1;char ch=getchar(); 14 while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 15 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 16 return x*f; 17 } 18 vector
             
               to[maxn]; 19 LL N,M; 20 LL a[maxn]; 21 LL dep[maxn],fa[maxn],son[maxn],top[maxn],siz[maxn],id[maxn]; 22 LL val[maxn]; 23 LL num; 24 inline void dfs1(LL rt,LL fath,LL deep){ 25 dep[rt]=deep; siz[rt]=1; fa[rt]=fath; 26 for(LL i=0;i
              
               >1; 57 build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); 58 tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; 59 } 60 inline void update_son(LL rt){ 61 LL d=tree[rt].lazy; 62 if(d!=0){ 63 tree[rt<<1].sum+=(tree[rt<<1].r-tree[rt<<1].l+1)*d; 64 tree[rt<<1|1].sum+=(tree[rt<<1|1].r-tree[rt<<1|1].l+1)*d; 65 tree[rt<<1].lazy+=d; tree[rt<<1|1].lazy+=d; 66 tree[rt].lazy=0; 67 } 68 } 69 inline void change(LL rt,LL l,LL r,LL delta){ 70 if(l<=tree[rt].l&&tree[rt].r<=r){ 71 tree[rt].sum+=(tree[rt].r-tree[rt].l+1)*delta; 72 tree[rt].lazy+=delta; 73 return ; 74 } 75 update_son(rt); 76 LL mid=(tree[rt].l+tree[rt].r)>>1; 77 if(l<=mid) change(rt<<1,l,r,delta); 78 if(mid+1<=r) change(rt<<1|1,l,r,delta); 79 tree[rt].sum=tree[rt<<1].sum+tree[rt<<1|1].sum; 80 } 81 inline LL query(LL rt,LL l,LL r){ 82 if(l<=tree[rt].l&&tree[rt].r<=r){ 83 return tree[rt].sum; 84 } 85 update_son(rt); 86 LL ans=0; 87 LL mid=(tree[rt].l+tree[rt].r)>>1; 88 if(l<=mid) ans+=query(rt<<1,l,r); 89 if(mid+1<=r) ans+=query(rt<<1|1,l,r); 90 return ans; 91 } 92 inline void ASK(LL x){ 93 LL tp=top[x],ans=0; 94 while(x!=0&&tp!=0){ 95 ans+=query(1,id[tp],id[x]); 96 x=fa[tp]; tp=top[x]; 97 } 98 printf("%lld\n",ans); 99 }100 int main(){101 N=read(); M=read();102 for(LL i=1;i<=N;i++) a[i]=read();103 for(LL i=1,u,v;i<=N-1;i++){104 u=read(); v=read();105 to[u].push_back(v); to[v].push_back(u);106 }107 dis[1]=a[1];108 dfs1(1,0,1); dfs2(1,1);109 for(LL i=1;i<=N;i++) val[id[i]]=a[i];110 build(1,1,num);111 for(LL i=1,kin;i<=M;i++){112 kin=read();113 if(kin==1){114 LL x=read(),d=read();115 change(1,id[x],id[x],d);116 }117 else if(kin==2){118 LL x=read(),d=read();119 change(1,id[x],id[x]+siz[x]-1,d);120 }121 else if(kin==3){122 LL x=read();123 ASK(x);124 }125 }126 return 0;127 }