记录编号	167011	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.627 s
提交时间	2015-06-19 19:55:11	内存使用	18.80 MiB

#include<cstdio>
#include<deque>
#include<iostream>
using namespace std;
typedef long long LL;
int N,M;
int f[100010]={0},siz[100010]={0},p[100010],dfn[100010]={0};
int st[100010]={0},en[100010]={0},dep[100010]={0},q[100010]={0};
int tot=0;
LL z[2][100010]={0},a[100010]={0};
deque<int> sw[100010],Q;
void make()
{
	st[1]=1;en[1]=N+1;dfn[1]=1;
	Q.push_back(1);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop_front();
		siz[x]=1;a[x]=p[x]+a[f[x]];dep[x]=dep[f[x]]+1;q[++tot]=x;
		for(int i=0;i<sw[x].size();i++)
		{
			int v=sw[x][i]; 
			if(f[x]==v) continue;
			f[v]=x;
			Q.push_back(v);
		}
		//cout<<x<<endl;
	}
	//cout<<1;
	for(int i=N;i>0;i--) siz[f[q[i]]]+=siz[q[i]];
	for(int i=1;i<=N;i++)
	{
		int now=i+1,last=dfn[i];
		for(int j=0;j<sw[last].size();j++)
		{
			int v=sw[last][j];
		    if(v==f[last])continue;
			dfn[now]=v;st[v]=now;
			//cout<<v<<" "<<now<<" ";
			now+=siz[v];en[v]=now;
			//cout<<now<<endl;
		}
		//cout<<last<<" ";
	}
}
void add(int x,LL v,bool t)
{
	while(x<=N) {z[t][x]+=v;x+=x&(-x);}
}
LL query(int x,bool t)
{
	LL re=0;
	while(x>0) {re+=z[t][x];x-=x&(-x);}
	return re;
}
int main()
{
    freopen("haoi2015_t2.in","r",stdin);
	freopen("haoi2015_t2.out","w",stdout);
	scanf("%d%d",&N,&M);
	int fr,to;
	for(int i=1;i<=N;i++)
		scanf("%d",&p[i]);
	for(int i=1;i<N;i++)
	{
		scanf("%d%d",&fr,&to);
		sw[fr].push_back(to);
		sw[to].push_back(fr);
	}
	make();
	int o,u,x;
	LL tem=0;
	for(int i=1;i<=M;i++)
	{
		scanf("%d",&o);
		if(o==1)
		{
			scanf("%d%d",&u,&x);
			add(st[u],x,0);add(en[u],-x,0);
		}
		if(o==2)
		{
			scanf("%d%d",&u,&x);
		    tem=1-dep[u];tem*=x;
			add(st[u],tem,0);add(en[u],-tem,0);
			add(st[u],x,1);add(en[u],-x,1);
		}
		if(o==3)
		{
			scanf("%d",&u);
			LL ans=a[u]+query(st[u],0)+query(st[u],1)*dep[u];
			printf("%lld\n",ans);
		}
	}
	return 0;
}