记录编号	161266	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	0.863 s
提交时间	2015-05-03 12:48:15	内存使用	17.10 MiB

/*
Problem:HAOI2015_T2;
Language:c++;
by dydxh;
2015.5.1;
*/
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<cstdio>
using namespace std;
const int maxn=100005;
const int oo=2000000000;
int n,m,cnt=0,len=0,yy,x;
int linkk[maxn],dep[maxn],l[maxn],r[maxn];
long long v[maxn],up_k,up_b;
struct seg
{
	long long k,b,delta_b,delta_k;
}tree[maxn<<2];
struct edge
{
	int y,next;
}e[maxn<<1];
inline int read()
{
	int 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-'0';ch=getchar();}
	return x*f;
}
void insert(int a,int b)
{
	e[++len].next=linkk[a];
	linkk[a]=len;
	e[len].y=b;
	e[++len].next=linkk[b];
	linkk[b]=len;
	e[len].y=a;
}
int id[maxn],stack[maxn],top=0;
void dfs()
{
	/*l[now]=++cnt,dep[now]=dep[father]+1,v[now]=v[father]+v[now];
	for(int i=linkk[now];i;i=e[i].next)
	{
		int tn=e[i].y;
		if(tn==father)
			continue;
		dfs(tn,now);
	}
	r[now]=cnt;*/
	memset(id,0,sizeof(id));
	memset(l,0,sizeof(l));
	memset(r,0,sizeof(r));
	for(int i=1;i<=n;i++)
		id[i]=linkk[i];
	stack[++top]=1,stack[0]=0;
	while(top)
	{
		int now=stack[top];
		if(!l[now])
			l[now]=++cnt,dep[now]=dep[stack[top-1]]+1,v[now]=v[stack[top-1]]+v[now];
		if(id[now])
		{
			int edgee=id[now];
			id[now]=e[edgee].next;
			if(e[edgee].y==stack[top-1])
				continue;
			stack[++top]=e[edgee].y;
		}
		else
			r[stack[top--]]=cnt;
	}
}
void up_data(int leftt,int rightt,int root)
{
	if(leftt>r[yy] || rightt<l[yy])
		return ;
	if(l[yy]<=leftt && rightt<=r[yy])
	{
		tree[root].delta_b+=up_b,tree[root].b+=up_b;
		tree[root].delta_k+=up_k,tree[root].k+=up_k;
		return ;
	}
	int mid=(leftt+rightt)>>1;
	up_data(leftt,mid,root<<1);
	up_data(mid+1,rightt,root<<1|1);
}
long long ask(int leftt,int rightt,int root)
{
	if(leftt>l[yy] || rightt<l[yy])
		return 0;
	if(l[yy]==leftt && rightt==l[yy])
		return 1LL*tree[root].k*dep[yy]+tree[root].b;
	if(tree[root].delta_b!=0)
	{
		tree[root<<1].delta_b+=tree[root].delta_b;
		tree[root<<1].b+=tree[root].delta_b;
		tree[root<<1|1].delta_b+=tree[root].delta_b;
		tree[root<<1|1].b+=tree[root].delta_b;
		tree[root].delta_b=0;
	}
	if(tree[root].delta_k!=0)
	{
		tree[root<<1].delta_k+=tree[root].delta_k;
		tree[root<<1].k+=tree[root].delta_k;
		tree[root<<1|1].delta_k+=tree[root].delta_k;
		tree[root<<1|1].k+=tree[root].delta_k;
		tree[root].delta_k=0;
	}
	int mid=(leftt+rightt)>>1;
	long long ll=ask(leftt,mid,root<<1);
	long long rr=ask(mid+1,rightt,root<<1|1);
	return rr+ll;
}
void dydxh()
{
	while(m--)
	{
		int opt=read();
		if(opt==1)
		{
			yy=read(),x=read();
			up_b=x,up_k=0;
			up_data(1,n,1);
		}
		else if(opt==2)
		{
			yy=read(),x=read();
			up_b=1LL*x*(1-dep[yy]),up_k=x;
			up_data(1,n,1);
		}
		else
		{
			yy=read();
			long long ans=ask(1,n,1)+v[yy];
			printf("%lld\n",ans);
		}
	}
}
int main()
{
	freopen("haoi2015_t2.in","r",stdin);
	freopen("haoi2015_t2.out","w",stdout);
	memset(tree,0,sizeof(tree));
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		v[i]=read();
	int a,b;
	for(int i=1;i<n;i++)
	{
		a=read(),b=read();
		insert(a,b);
	}
	dep[0]=-1,v[0]=0;
	dfs();
	dydxh();
	//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
	return 0;
}