有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个

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

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

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

鸣谢bhiaibogf提供

  1 /*by SilverN*/  2 #include<iostream>  3 #include<algorithm>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #define ls l,mid,rt<<1  8 #define rs mid+1,r,rt<<1|1  9 #define LL long long 10 using namespace std; 11 const int mxn=100010; 12 int read(){ 13     int 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 int n,m; 19 struct edge{ 20     int v,nxt; 21 }e[mxn<<1]; 22 int hd[mxn],mct=0; 23 void add_edge(int u,int v){ 24     e[++mct].v=v;e[mct].nxt=hd[u];hd[u]=mct;return; 25 } 26 struct node{ 27     int w,e; 28     int top,f,son; 29     int size,dep; 30 }tr[mxn]; 31 struct segtree{ 32     LL sum,mk; 33 }st[mxn<<2]; 34 int sz=0; 35 int w[mxn]; 36 void DFS1(int u){ 37     tr[u].size=1;tr[u].son=0; 38     for(int i=hd[u];i;i=e[i].nxt){ 39         int v=e[i].v; 40         if(v==tr[u].f)continue; 41         tr[v].f=u; 42         tr[v].dep=tr[u].dep+1; 43         DFS1(v); 44         tr[u].size+=tr[v].size; 45         if(tr[v].size>tr[tr[u].son].size)tr[u].son=v; 46     } 47     return; 48 } 49 void DFS2(int u,int top){ 50     tr[u].top=top; 51     tr[u].w=++sz; 52     if(tr[u].son){ 53         DFS2(tr[u].son,top); 54         for(int i=hd[u];i;i=e[i].nxt){ 55             int v=e[i].v; 56             if(v!=tr[u].f && v!=tr[u].son){ 57                 DFS2(v,v); 58             } 59         } 60     } 61     tr[u].e=sz; 62     return; 63 } 64 void pushdown(int l,int r,int rt){ 65     if(l==r)return; 66     st[rt<<1].mk+=st[rt].mk;st[rt<<1|1].mk+=st[rt].mk; 67     int mid=(l+r)>>1; 68     st[rt<<1].sum+=st[rt].mk*(mid-l+1); 69     st[rt<<1|1].sum+=st[rt].mk*(r-mid); 70     st[rt].mk=0; 71     return; 72 } 73 void add(int L,int R,int v,int l,int r,int rt){ 74     if(L<=l && r<=R){ 75         st[rt].sum+=(LL)v*(r-l+1); 76         st[rt].mk+=v; 77         return; 78     } 79     if(st[rt].mk)pushdown(l,r,rt); 80     int mid=(l+r)>>1; 81     if(L<=mid)add(L,R,v,ls); 82     if(R>mid)add(L,R,v,rs); 83     st[rt].sum=st[rt<<1].sum+st[rt<<1|1].sum; 84     return; 85 } 86 long long qsum(int L,int R,int l,int r,int rt){ 87     if(L<=l && r<=R)return st[rt].sum; 88     if(st[rt].mk)pushdown(l,r,rt); 89     int mid=(l+r)>>1; 90     LL res=0; 91     if(L<=mid)res+=qsum(L,R,ls); 92     if(R>mid)res+=qsum(L,R,rs); 93     return res; 94 } 95 long long findsum(int x){ 96     LL res=0; 97     while(tr[x].top!=1){ 98         res+=qsum(tr[tr[x].top].w,tr[x].w,1,n,1); 99         x=tr[tr[x].top].f;100     }101     res+=qsum(1,tr[x].w,1,n,1);102     return res;103 }104 int main(){105     n=read();m=read();106     int i,j,u,v,op,x,a;107     for(i=1;i<=n;i++)w[i]=read();108     for(i=1;i<n;i++){109         u=read();v=read();110         add_edge(u,v);111         add_edge(v,u);112     }113     DFS1(1);114     DFS2(1,1);115     for(i=1;i<=n;i++)116         add(tr[i].w,tr[i].w,w[i],1,n,1);117 /*  for(i=1;i<=n;i++)118         printf("%d ",qsum(tr[i].w,tr[i].w,1,n,1));119     printf("\n");*/120     for(i=1;i<=m;i++){121         op=read();122         switch(op){123             case 1:{124                 x=read();a=read();125                 add(tr[x].w,tr[x].w,a,1,n,1);126                 break;127             }128             case 2:{129                 x=read();a=read();130                 add(tr[x].w,tr[x].e,a,1,n,1);131                 break;132             }133             case 3:{134                 x=read();135                 printf("%lld\n",findsum(x));136                 break;137             }138         }139     }140     return 0;141 }