记录编号	413454	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.802 s
提交时间	2017-06-11 16:35:28	内存使用	15.58 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=100010;
typedef long long ll;
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
inline int read(){
  int s=0,f=1; char ch=getchar(); 
  while(ch>'9'||ch<'0'){if(ch=='-')f=-1; ch=getchar();}
  while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();}
  return s*f;      
}
int n,m,a[maxn],r[maxn],tot;
struct oo{
  int fr,to,next;       
}c[2*maxn];
inline void add(int x,int y){
  c[tot].fr=x;
  c[tot].to=y;
  c[tot].next=r[x];
  r[x]=tot++; 
}
ll size[maxn],pos[maxn],deep[maxn],son[maxn],fa[maxn];
inline void dfs1(int x){
  size[x]=1; son[x]=0;
  for(int i=r[x];i!=-1;i=c[i].next)
   if(c[i].to!=fa[x]){
    fa[c[i].to]=x;
    deep[c[i].to]=deep[x]+1;
    dfs1(c[i].to);
    size[x]+=size[c[i].to];
    if(size[son[x]]<size[c[i].to])
     son[x]=c[i].to;                  
   }       
}
ll top[maxn],cnt,fir[maxn],la[maxn];
inline void dfs2(int u,int v){
  top[u]=v;
  fir[u]=la[u]=++cnt;
  pos[cnt]=u;
  if(son[u]) dfs2(son[u],v);
  for(int i=r[u];i!=-1;i=c[i].next)
   if(c[i].to!=fa[u]&&c[i].to!=son[u])
    dfs2(c[i].to,c[i].to); 
  la[u]=cnt;           
}
long long sum[4*maxn];
inline void build(int root,int l,int r){
  if(l==r){
   sum[root]=a[pos[l]];
   return ;         
  }       
  int mid=(l+r)>>1;
  build(lson); build(rson);
  sum[root]=sum[root<<1]+sum[root<<1|1];
}
long long addd[4*maxn];
inline void pushdown(int rt,long long len){
  if(addd[rt]){
   addd[rt<<1]+=addd[rt];
   addd[rt<<1|1]+=addd[rt];
   sum[rt<<1]+=addd[rt]*(len-(len>>1));
   sum[rt<<1|1]+=addd[rt]*(len>>1);
   addd[rt]=0;             
  }     
}
inline long long query(int L,int R,int root,int l,int r){
  if(L<=l&&R>=r) return sum[root];
  pushdown(root,r-l+1);
  int mid=(l+r)>>1;
  long long ans=0;
  if(L<=mid) ans+=query(L,R,lson);
  if(R>mid) ans+=query(L,R,rson);    
  return ans;   
}
inline ll Query(int x,int y){
  ll fx=top[x],fy=top[y],ans=0;
  while(fx^fy){
   if(deep[fx]<deep[fy]){
    swap(fx,fy);
    swap(x,y);                      
   }          
   ans+=query(fir[fx],fir[x],1,1,n); 
   x=fa[fx]; 
   fx=top[x];  
  }       
  if(deep[x]>deep[y]) swap(x,y);
  ans+=query(fir[x],fir[y],1,1,n);
  return ans;
}
inline void update(int L,int R,ll val,int root,int l,int r){
  if(L<=l&&r<=R){
   addd[root]+=val;
   sum[root]+=(ll)(r-l+1)*val;
   return ;               
  }       
  pushdown(root,r-l+1);
  int mid=(r+l)>>1;
  if(L<=mid) update(L,R,val,lson);
  if(R>mid) update(L,R,val,rson);
  sum[root]=sum[root<<1]+sum[root<<1|1];
}
 
void out(){
  printf("\n");
  for(int i=1;i<=n;i++)
    printf("%d ",query(fir[i],fir[i],1,1,n));     
  printf("\n");
}
 
int main(){
  freopen("haoi2015_t2.in","r",stdin);
  freopen("haoi2015_t2.out","w",stdout);
  n=read(),m=read();
  r[0]=-1;
  for(int i=1;i<=n;i++){ 
   a[i]=read();
   r[i]=-1;
  }
  for(int i=1;i<n;i++){
   int x=read(),y=read();
   add(x,y); add(y,x);       
  }
  dfs1(1); dfs2(1,1); build(1,1,n);
  for(int i=1;i<=m;i++){
   int pan=read();
   if(pan==1){
     int x=read(),y=read();
     update(fir[x],fir[x],y,1,1,n);            
   }        
   if(pan==2){
    int x=read(),y=read();
    update(fir[x],la[x],y,1,1,n);           
   }
   if(pan==3){
    //out();
    int x=read();
    printf("%lld\n",Query(1,x));         
   }
  }
  //while(1);
  return 0;
}