记录编号	272141	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.425 s
提交时间	2016-06-16 17:03:03	内存使用	53.72 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<fstream>
#include<algorithm>
#define lch l,mid,rt<<1
#define rch mid+1,r,rt<<1|1
using namespace std;
#define MINE
#ifdef MINE
ifstream fin("haoi2015_t2.in");
ofstream fout("haoi2015_t2.out");
#else
#define fin cin
#define fout cout
#endif
const int maxn=500010;
struct edge{
	int to;
	edge *prev;
}ee[maxn];
void insert(int,int);
void dfs1(int);
void dfs2(int,int);
void build(int,int,int);
void add(int,int,long long,int,int,int);
long long query(int,int,int,int,int);
void update(int,int,int);
long long Query(int,int);
int len=0;
edge *last[maxn];
int prt[maxn],tim=0,first[maxn],finish[maxn],top[maxn];
int depth[maxn],data[maxn],son[maxn],size[maxn],id[maxn];
long long a[maxn<<2],lazy[maxn<<2];
int n,m;
int main(){
	ios::sync_with_stdio(false);
	fin>>n>>m;
	for(int i=1;i<=n;i++)fin>>data[i];
	for(int i=1,x,y;i<n;i++){
		fin>>x>>y;
		insert(x,y);
		insert(y,x);
	}
	depth[1]=1;
	dfs1(1);
	dfs2(1,1);
	build(1,n,1);
	while(m--){
		int z,x;
		long long y;
		fin>>z>>x;
		if(z==1){
			fin>>y;
			add(first[x],first[x],y,1,n,1);
		}
		else if(z==2){
			fin>>y;
			add(first[x],finish[x],y,1,n,1);
		}
		else if(z==3){
			fout<<Query(1,x)<<'\n';
		}
	}
	return 0;
}
void insert(int x,int y){
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
void dfs1(int x){
	size[x]=1;
	for(edge *e=last[x];e;e=e->prev){
		int y=e->to;
		if(y!=prt[x]){
			prt[y]=x;
			depth[y]=depth[x]+1;
			dfs1(y);
			size[x]+=size[y];
			if(size[y]>size[son[x]])son[x]=y;
		}
	}
}
void dfs2(int x,int tp){
	first[x]=++tim;
	id[tim]=x;
	top[x]=tp;
	if(son[x])dfs2(son[x],tp);
	for(edge *e=last[x];e;e=e->prev){
		int y=e->to;
		if(y^prt[x]&&y^son[x])dfs2(y,y);
	}
	finish[x]=tim;
}
void build(int l,int r,int rt){
	if(l==r){
		a[rt]=data[id[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(lch);
	build(rch);
	a[rt]=a[rt<<1]+a[rt<<1|1];
}
void add(int s,int t,long long num,int l,int r,int rt){
	if(s<=l&&t>=r){
		a[rt]+=(long long)(r-l+1)*num;
		lazy[rt]+=num;
		return;
	}
	update(l,r,rt);
	int mid=(l+r)>>1;
	if(s<=mid)add(s,t,num,lch);
	if(t>mid)add(s,t,num,rch);
	a[rt]=a[rt<<1]+a[rt<<1|1];
}
long long query(int s,int t,int l,int r,int rt){
	if(s<=l&&t>=r)return a[rt];
	update(l,r,rt);
	int mid=(l+r)>>1;
	if(t<=mid)return query(s,t,l,mid,rt<<1);
	if(s>mid)return query(s,t,mid+1,r,rt<<1|1);
	return query(s,t,lch)+query(s,t,rch);
}
void update(int l,int r,int rt){
	int mid=(l+r)>>1;
	a[rt<<1]+=(long long)(mid-l+1)*lazy[rt];
	lazy[rt<<1]+=lazy[rt];
	a[rt<<1|1]+=(long long)(r-mid)*lazy[rt];
	lazy[rt<<1|1]+=lazy[rt];
	lazy[rt]=0;
}
long long Query(int x,int y){
	long long ans=0;
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(depth[fx]<depth[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		ans+=query(first[fx],first[x],1,n,1);
		x=prt[fx];
		fx=top[x];
	}
	if(depth[x]>depth[y])swap(x,y);
	ans+=query(first[x],first[y],1,n,1);
	return ans;
}