记录编号	303614	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	沉迷学习的假的Keller	是否通过	通过
代码语言	C++	运行时间	3.017 s
提交时间	2016-09-06 09:05:31	内存使用	51.78 MiB

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#define lint long long
using namespace std;
const int maxn=500000+10;
int n,m;
lint a[maxn];
vector<int> e[maxn];

long long read(){
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
//===============================================//
// 			Heavy-Light Decomposition            //
//===============================================//
int dep[maxn],siz[maxn],fa[maxn],id[maxn],son[maxn],val[maxn],top[maxn],last[maxn],pos[maxn];
int dfs_clock;
void dfs1(int u,int d,int fath){
	dep[u]=d;
	siz[u]=1;
	son[u]=0;
	fa[u]=fath;
	for(int i=0;i<e[u].size();i++){
		int now=e[u][i];
		if(now==fath) continue;
		dfs1(now,d+1,u);
		siz[u]+=siz[now];
		if (siz[son[u]]<siz[now]){
			son[u]=now; 
		}
	}
	return ;
}

void dfs2(int u,int tp){
	top[u]=tp;
	id[u]= ++dfs_clock;
	pos[dfs_clock]=u;
	if(son[u]) dfs2(son[u],tp);
	for(int i=0;i<e[u].size();i++){
		int now=e[u][i];
		if(now!=fa[u]&&now!=son[u]){
			dfs2(now,now);	
		}
	}
	last[u]=dfs_clock;
	return ;
}

void HLD(){
	dep[1]=1;
	dfs1(1,1,0);
	dfs2(1,1);
	return ;	
}

//==============================================//
//                 Segment tree                 // 
//==============================================// 

lint sum[4*maxn],lazy[4*maxn];

void pushup(int x){
	sum[x]=sum[x*2]+sum[x*2+1];
}

void pushdown(int id,int l,int r){
	int mid=(l+r)>>1;
	lazy[id*2]+=lazy[id];sum[id*2]+=(lint)lazy[id]*(mid+1-l);
	lazy[id*2+1]+=lazy[id];sum[id*2+1]+=(lint)lazy[id]*(r-mid);
	lazy[id]=0;
	return ;
}

void build(int id,int l,int r){
	if(l==r){
		sum[id]=a[pos[l]];
		return ;
	}
	int mid=(l+r)>>1;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	pushup(id);
}

void add(int id,int l,int r,int x,int y,lint val){
	if(x<=l&&r<=y){
		sum[id]+=val*(r-l+1);
		lazy[id]+=val;
		return ;	
	}
	pushdown(id,l,r);
	int mid=(l+r)>>1;
	if(x<=mid){
		add(id*2,l,mid,x,y,val);	
	}
	if(y>mid){
		add(id*2+1,mid+1,r,x,y,val);	
	}
	pushup(id);
}

lint query(int id,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return sum[id];
	}
	pushdown(id,l,r);
	int mid=(l+r)>>1;
	lint ans=0;
	if(x<=mid) ans+=query(id*2,l,mid,x,y);
	if(mid<y) ans+=query(id*2+1,mid+1,r,x,y);
	return ans;
}

//================================================

lint solve(int x,int y){
	lint ans=0;
	int tp1=top[x],tp2=top[y];
	while(tp1!=tp2){
		if(dep[tp1]<dep[tp2]){
			swap(tp1,tp2);  
            swap(x,y);	
		}
		ans+=query(1,1,n,id[tp1],id[x]);  
        x=fa[tp1]; 
        tp1=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	ans+=query(1,1,n,id[x],id[y]);
	return ans;
}

int main(){
	freopen("haoi2015_t2.in","r",stdin);
	freopen("haoi2015_t2.out","w",stdout);
	n=read();
	m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
	}
	for(int i=1;i<n;i++){
		lint x,y;
		x=read();
		y=read();
		e[x].push_back(y);
		e[y].push_back(x);
	}
	HLD();
	build(1,1,n);
	while(m--){
		int p,x;
		long long y;
		scanf("%d%d",&p,&x);
		if(p==1){
			y=read();
			add(1,1,n,id[x],id[x],y);
		}
		else if(p==2){
			y=read();
			add(1,1,n,id[x],last[x],y);
		}
		else if(p==3){
			printf("%lld\n",solve(1,x));
		}
	}
	return 0;
}