记录编号	307929	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	521	是否通过	通过
代码语言	C++	运行时间	1.828 s
提交时间	2016-09-16 15:51:24	内存使用	83.10 MiB

#include<stdio.h>
#define LL long long
inline void read(int&x)
{
	char ch;bool flag=false;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')flag=1;
	x=ch^'0';
	while(ch=getchar(),ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^'0');
	if(flag) x=-x;
}
const int Size=1000010;
int last[Size],son[Size],fa[Size],siz[Size],top[Size],dep[Size],tid[Size],rank[Size],tn;
LL sum[Size<<2],lazy[Size<<2],val[Size];
int to[Size<<1],next[Size<<1],head[Size],num;
inline void add(int u,int v)
{
	to[++num]=v,next[num]=head[u],head[u]=num;
}
void dfs1(int u,int f,int d)
{
	son[u]=0,fa[u]=f,siz[u]=1,dep[u]=d;
	for(int i=head[u];i;i=next[i]){
		int v=to[i];
		if(v==f) continue;
		dfs1(v,u,d+1);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp,tid[u]=++tn,rank[tid[u]]=u;
	if(son[u]) dfs2(son[u],tp);
	for(int i=head[u];i;i=next[i])
		if(to[i]!=son[u]&&to[i]!=fa[u])
			dfs2(to[i],to[i]);
	last[u]=tn;
}
void build(int l,int r,int rt)
{
	if(l>r) return ;
	if(l==r){
		sum[rt]=val[rank[l]];
		return ;
	}
	int mid=l+r>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
inline void pushdown(int rt,int x)
{
	if(!lazy[rt]) return ;
	lazy[rt<<1]+=lazy[rt];
	lazy[rt<<1|1]+=lazy[rt];
	sum[rt<<1]+=lazy[rt]*(x-(x>>1));
	sum[rt<<1|1]+=lazy[rt]*(x>>1);
	lazy[rt]=0;
}
void update(int L,int R,LL x,int l,int r,int rt)
{
	if(L>R||l>r) return ;
	if(l>=L&&r<=R){
		sum[rt]+=x*(r-l+1);
		lazy[rt]+=x;
		return ;
	}
	pushdown(rt,r-l+1);
	int mid=l+r>>1;
	if(mid>=L) update(L,R,x,l,mid,rt<<1);
	if(mid<R) update(L,R,x,mid+1,r,rt<<1|1);
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
inline void swap(int &x,int &y){x^=y,y^=x,x^=y;}
LL query(int L,int R,int l,int r,int rt)
{
	if(L>R||l>r) return 0;
	if(l>=L&&r<=R) return sum[rt];
	pushdown(rt,r-l+1);
	int mid=l+r>>1;
	LL ret=0;
	if(mid>=L) ret+=query(L,R,l,mid,rt<<1);
	if(mid<R) ret+=query(L,R,mid+1,r,rt<<1|1);
	return ret;
}
LL find(int u,int v)
{
	LL ret=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		ret+=query(tid[top[u]],tid[u],1,tn,1);
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	ret+=query(tid[u],tid[v],1,tn,1);
	return ret;
}
int _521()
{
#define COGS
#ifdef COGS
	freopen("haoi2015_t2.in","r",stdin);
	freopen("haoi2015_t2.out","w",stdout);
#else
	freopen("1.in","r",stdin);
#endif
	int i,n,m;
	read(n),read(m);
	for(i=1;i<=n;i++) scanf("%lld",&val[i]);
	for(i=1;i<n;i++){
		int u,v;
		read(u),read(v);
		add(u,v),add(v,u);
	}
	dfs1(1,0,1),dfs2(1,1);
	build(1,tn,1);
	while(m--){
		int a,b;LL c;
		read(a);
		if(a==1){
			read(b),scanf("%lld",&c);
			update(tid[b],tid[b],c,1,tn,1);
		}else if(a==2){
			read(b),scanf("%lld",&c);
			update(tid[b],last[b],c,1,tn,1);
		}else{
			read(b);
			printf("%lld\n",find(1,b));
		}
	}
	return 0;
}
int _520=_521();
int main(){;}