记录编号	416435	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	1.384 s
提交时间	2017-06-21 16:39:07	内存使用	6.90 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const long long maxn=1e5+5;
struct edge
{
	long long cu;
	edge *nt;
	edge(){nt=NULL;}
}*head[maxn];
struct stree
{
	long long l,r;
	long long va;
	long long lazy;
	stree *ls,*rs,*fa;
	stree(){ls=rs=fa=NULL;va=lazy=0;}
}*root;
long long n,m;
long long fr,to;
long long c,x,a;
long long dfsn=1;
long long N[maxn];
long long siz[maxn],top[maxn],fa[maxn],son[maxn];
long long dfn[maxn],atdfn[maxn],trn[maxn];
bool jud[maxn];
void add();
void sa(stree *now,long long l,long long r);
void aa(stree *now,long long nl,long long nr,long long l,long long r);
void pushup(stree *now);
void pushdown(stree *now,long long l,long long r);
long long dfs_a(edge *now,long long cur);
long long dfs_b(edge *now,long long cur);
long long chain(long long cur);
long long search(stree *now,long long nl,long long nr,long long l,long long r);
stree* build(long long l,long long r);
int main()
{
	freopen("haoi2015_t2.in","r",stdin);
	freopen("haoi2015_t2.out","w",stdout);
	memset(son,-1,sizeof(son));
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=n;i++)scanf("%lld",&N[i]);
	for(long long i=1;i<n;i++)
	{
		scanf("%lld%lld",&fr,&to);
		add();
	}
	fa[1]=1;
	dfs_a(head[1],1);
	memset(jud,0,sizeof(jud));
	top[1]=1;
	dfs_b(head[1],1);
	root=build(1,n);
	fa[1]=0;
	for(long long i=1;i<=m;i++)
	{
		scanf("%lld",&c);
		if(c==1)
		{
			scanf("%lld%lld",&x,&a);
			sa(root,1,n);
		}
		if(c==2)
		{
			scanf("%lld%lld",&x,&a);
			aa(root,dfn[x],dfn[trn[x]],1,n);
		}
		if(c==3)
		{
			scanf("%lld",&x);
			printf("%lld\n",chain(x));
		}
	}
}
long long chain(long long cur)
{
	long long sum=0;
	while(cur!=0)
	{
		if(top[cur]==cur)
		{
			sum+=search(root,dfn[cur],dfn[cur],1,n);
			cur=fa[cur];
		}
		else
		{
			sum+=search(root,dfn[top[cur]],dfn[cur],1,n);
			cur=fa[top[cur]];
		}
	}
	return sum;
}
long long search(stree *now,long long nl,long long nr,long long l,long long r)
{
	if(now->lazy)pushdown(now,l,r);
	if(l==nl&&r==nr)return now->va;
	long long mid=(l+r)>>1;
	if(nr<=mid)return search(now->ls,nl,nr,l,mid);
	if(nl>mid)return search(now->rs,nl,nr,mid+1,r);
	return search(now->ls,nl,mid,l,mid)+search(now->rs,mid+1,nr,mid+1,r);
}
void pushdown(stree *now,long long l,long long r)
{
	now->va+=(r-l+1)*now->lazy;
	if(now->ls==NULL)
	{
		now->lazy=0;
		return;
	}
	now->ls->lazy+=now->lazy;
	now->rs->lazy+=now->lazy;
	now->lazy=0;
}
void pushup(stree *now)
{
	while(now!=NULL)
	{
		if(now->ls->lazy)pushdown(now->ls,now->ls->l,now->ls->r);
		if(now->rs->lazy)pushdown(now->rs,now->rs->l,now->rs->r);
		now->va=now->ls->va+now->rs->va;
		now=now->fa;
	}
}
void aa(stree *now,long long nl,long long nr,long long l,long long r)
{
	if(now->lazy)pushdown(now,l,r);
	if(l==nl&&r==nr)
	{
		now->va+=(r-l+1)*a;
		pushup(now->fa);
		if(now->ls==NULL)return;
		now->ls->lazy+=a;
		now->rs->lazy+=a;
		return;
	}
	long long mid=(l+r)>>1;
	if(nr<=mid)aa(now->ls,nl,nr,l,mid);
	else if(nl>mid)aa(now->rs,nl,nr,mid+1,r);
	else
	{
		aa(now->ls,nl,mid,l,mid);
		aa(now->rs,mid+1,nr,mid+1,r);
	}
}
void sa(stree *now,long long l,long long r)
{
	if(l==r)
	{
		now->va+=a;
		pushup(now->fa);
		return;
	}
	long long mid=(l+r)>>1;
	if(dfn[x]<=mid)sa(now->ls,l,mid);
	else sa(now->rs,mid+1,r);
//	now->va=now->ls->va+now->rs->va;
}
stree* build(long long l,long long r)
{
	stree *p=new stree();
	p->l=l;p->r=r;
	if(l==r)
	{
		p->va=N[atdfn[l]];
		return p;
	}
	long long mid=(l+r)>>1;
	p->ls=build(l,mid);
	p->rs=build(mid+1,r);
	p->ls->fa=p;
	p->rs->fa=p;
	p->va=p->ls->va+p->rs->va;
	return p;
}
long long dfs_b(edge *now,long long cur)
{
	jud[cur]=1;
	dfn[cur]=dfsn;
	atdfn[dfsn++]=cur;
	if(son[cur]==-1)
	{
		trn[cur]=cur;
		return trn[cur];
	}
	top[son[cur]]=top[cur];
	trn[cur]=trn[dfs_b(head[son[cur]],son[cur])];
	while(now!=NULL)
	{
		if(now->cu==son[cur]||jud[now->cu])
		{
			now=now->nt;
			continue;
		}
		top[now->cu]=now->cu;
		trn[cur]=trn[dfs_b(head[now->cu],now->cu)];
		now=now->nt;
	}
	return cur;
}
long long dfs_a(edge *now,long long cur)
{
	jud[cur]=1;
	if(now==NULL)
	{
		siz[cur]=1;
		return cur;
	}
	while(now!=NULL)
	{
		if(jud[now->cu])
		{
			now=now->nt;
			continue;
		}
		fa[dfs_a(head[now->cu],now->cu)]=cur;
		if(son[cur]==-1||siz[son[cur]]<siz[now->cu])son[cur]=now->cu;
		siz[cur]+=siz[now->cu];
		now=now->nt;
	}
	siz[cur]++;
	return cur;
}
void add()
{
	edge *p=new edge();
	p->cu=to;
	p->nt=head[fr];
	head[fr]=p;
	edge *ep=new edge();
	ep->cu=fr;
	ep->nt=head[to];
	head[to]=ep;
}