记录编号	318974	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	Ostmbh	是否通过	通过
代码语言	C++	运行时间	1.420 s
提交时间	2016-10-10 07:55:40	内存使用	14.43 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX=100000+10;
int head[MAX]={0},next[MAX<<1]={0},to[MAX<<1];
int dep[MAX];
int son[MAX]={0};
int size[MAX]={0};
int tid[MAX];
int fa[MAX];
int top[MAX];
int rank[MAX];
int A[MAX];
struct T{
	int l,r;
	long long addv,summ;
}T[MAX<<2];
#define lson o<<1,L,mid
#define rson o<<1|1,mid+1,R
int ql,qr;
int n;
inline void build(int o,int L,int R){
	T[o].addv=0;
	T[o].l=L;
	T[o].r=R;
	if(L==R){
		T[o].summ=A[rank[L]];
		return ;
	}
	int mid=(L+R)>>1;
	build(lson);
	build(rson);
	T[o].summ=T[o<<1].summ+T[o<<1|1].summ;
}
inline void pushdown(int o){
	T[o<<1].addv+=T[o].addv;
	T[o<<1].summ+=T[o].addv*(T[o<<1].r-T[o<<1].l+1);
	T[o<<1|1].addv+=T[o].addv;
	T[o<<1|1].summ+=T[o].addv*(T[o<<1|1].r-T[o<<1|1].l+1);
	T[o].addv=0;
}
inline void add(int o,long long ad,int l,int r){
	if(T[o].l>=l&&T[o].r<=r){
		T[o].addv+=ad;
		T[o].summ+=ad*(T[o].r-T[o].l+1);
		return ;
	}
	else if(T[o].l!=T[o].r){
		if(T[o].addv)
			pushdown(o);
		int mid=(T[o].l+T[o].r)>>1;
		if(mid>=l)
			add(o<<1,ad,l,r);
		if(mid<r)
			add(o<<1|1,ad,l,r);
		T[o].summ=T[o<<1].summ+T[o<<1|1].summ;
	}
}
inline long long sum(int o,int l,int r){
	long long ans=0;
	if(T[o].l>=l&&T[o].r<=r)
		return T[o].summ;
	else if(T[o].l!=T[o].r){
		int mid=(T[o].l+T[o].r)>>1;
		if(T[o].addv)
			pushdown(o);
		if(mid>=l)
			ans+=sum(o<<1,l,r);
		if(mid<r)
			ans+=sum(o<<1|1,l,r);
		return ans;
	}
}
inline void Add1(int x,int y){
	add(1,y,tid[x],tid[x]);
}
inline void Add2(int x,int y){
	add(1,y,tid[x],tid[x]+size[x]-1);
}
inline long long Sum(int x){
	long long ans=0;
	while(1!=top[x]){
		ans+=sum(1,tid[top[x]],tid[x]);
		x=fa[top[x]];
	}
	ans+=sum(1,1,tid[x]);
	return ans;
}
int ind=0,edge=1;
inline void addedge(int x,int y){
	to[edge]=y,next[edge]=head[x],head[x]=edge++;
	to[edge]=x,next[edge]=head[y],head[y]=edge++;
}
inline void dfs1(int x,int p,int d){
	dep[x]=d;
	fa[x]=p;
	size[x]=1;
	for(int i=head[x];i;i=next[i]){
		if(to[i]!=p){
			dfs1(to[i],x,d+1);
			size[x]+=size[to[i]];
			if(!son[x]||size[to[i]]>size[son[x]]){
				son[x]=to[i];
			}
		}
	}
}
inline void dfs2(int x,int p){
	top[x]=p;
	tid[x]=++ind;
	rank[tid[x]]=x;
	if(!son[x])
		return ;
	dfs2(son[x],p);
	for(int i=head[x];i;i=next[i]){
		if(to[i]!=fa[x]&&to[i]!=son[x])
			dfs2(to[i],to[i]);
	}
}
inline void read(int &x){
	x=0;
	int f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')
			f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	x=x*f;
}
int main(){
	freopen("haoi2015_t2.in","r",stdin);
	freopen("haoi2015_t2.out","w",stdout);
	int m;
	read(n),read(m);
	for(int i=1;i<=n;i++)
		read(A[i]);
	int x,y;
	for(int i=1;i<n;i++){
		read(x),read(y);
		addedge(x,y);
	}
	dfs1(1,1,1);
	dfs2(1,1);
	build(1,1,n);
	int z;
	for(int i=1;i<=m;i++){
		read(x),read(y);
		if(x!=3)
			read(z);
		if(x==1)
			Add1(y,z);
		else if(x==2)
			Add2(y,z);
		else if(x==3)
			printf("%lld\n",Sum(y));
	}
return 0;
}