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

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long
int n,m,x,y,z,w[200001];
int adj[200001],num;
ll add[400001],zh[400001];
struct kk
{
	int s,t,next;
}k[200001];
void swap(ll &a,ll &b){
	ll c=a;
	a=b;
	b=c;
}
inline int read(){
	int zh=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		zh=zh*10+ch-'0';
		ch=getchar();
	}
	return zh*f;
}
inline void pushup(int i)
{
    zh[i]=zh[i<<1]+zh[i<<1|1];
}
void init(int x,int y){
	k[num].s=x;
	k[num].t=y;
	k[num].next=adj[x];
	adj[x]=num++;
}
int fa[100001],dp[100001],son[100001],size[100001];
void Dfs1(int x,int father,int dep){
	fa[x]=father;dp[x]=dep;
	size[x]=1;son[x]=0;
	for(int i=adj[x];i!=-1;i=k[i].next){
		int o=k[i].t;
		if(o!=father){
			Dfs1(o,x,dep+1);
			size[x]+=size[o];
			if(size[son[x]]<size[o])
				son[x]=o;
		}
	}
}
int top[100001],id[100001],cnt,pos[100001];
int wcx[100001],yl[100001];//记得某皮说过：只可意会不可言传~ 
void Dfs2(int u,int tp){
	top[u]=tp;id[u]=++cnt;
	pos[cnt]=u;wcx[u]=cnt;
	if(son[u])
		Dfs2(son[u],tp);
	for(int i=adj[u];i!=-1;i=k[i].next){
		int o=k[i].t;
		if(o!=fa[u]&&o!=son[u]){
			Dfs2(o,o);
		}
	}	
	yl[u]=cnt;
}
void build(int l,int r,int x){
	add[x]=0;
	if(l==r){
		zh[x]=w[pos[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	zh[x]=zh[x<<1]+zh[x<<1|1];
}
void pushd(int x,int len){
	if(add[x]){
		add[x<<1]+=add[x];
		add[x<<1|1]+=add[x];
		zh[x<<1]+=add[x]*(len-(len>>1));
		zh[x<<1|1]+=add[x]*(len>>1);
		add[x]=0;
	}
}
void update(int L,int R,ll c,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
      add[rt]+=c;
      zh[rt]+=(ll)c*(r-l+1);
      return;
    }
    pushd(rt,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid)
      update(L,R,c,l,mid,2*rt);
    if(mid<R)
      update(L,R,c,mid+1,r,2*rt+1);
    pushup(rt);
}
ll ask(int s,int t,int l,int r,int x){
    if(s<=l&&t>=r) return zh[x];
    pushd(x,r-l+1);
    int mid=(l+r)>>1;ll ans=0;
    if(s<=mid) ans+=ask(s,t,l,mid,2*x);
    if(t>mid) ans+=ask(s,t,mid+1,r,2*x+1);
    return ans;
}
ll query(int x,int y){
    int fx=top[x],fy=top[y];
    ll res=0;
    while(fx^fy){
        if(dp[fx]<dp[fy]){
            swap(x,y);
            swap(fx,fy);
        }
        res+=ask(id[fx],id[x],1,n,1);
        x=fa[fx];fx=top[x];
    }
    if(dp[x]>dp[y]) swap(x,y);
    res+=ask(id[x],id[y],1,n,1);
    return res;
}
int main()
{
	freopen("haoi2015_t2.in","r",stdin);
	freopen("haoi2015_t2.out","w",stdout);
	memset(adj,-1,sizeof(adj));
	n=read();m=read();
	for(int i=1;i<=n;++i)
		w[i]=read();
	for(int i=1;i<n;++i){
		x=read();y=read();
		init(x,y);
		init(y,x);
	}
	Dfs1(1,0,0);
	Dfs2(1,1);
	build(1,n,1);
	for(int i=1;i<=m;++i){
		x=read();
		if(x==1){
			y=read();z=read();
			update(wcx[y],wcx[y],z,1,n,1);
		}
		if(x==2){
			y=read();z=read();
			update(wcx[y],yl[y],z,1,n,1);
		}
		if(x==3){
			y=read();
			printf("%lld\n",query(1,y));
		}
	}
	// while(1);
	return 0;
}