记录编号	160449	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.028 s
提交时间	2015-04-27 15:25:35	内存使用	9.85 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<vector>
using namespace std;
typedef long long LL;
const int SIZEN=100010,SIZEM=200010;
int N,M;
class Edge{
public:
	int to;
	int nxt;
};
Edge edges[SIZEM];
int tot=0;
int head[SIZEN];
LL val[SIZEN];
LL lis_val[SIZEN];
int father[SIZEN];
int lis_fa[SIZEN];
int subsz[SIZEN];
int dfn[SIZEN];
int dfslis[SIZEN];
int timer=0;
int BN,Bsize;
int start[SIZEN],end[SIZEN];
int belong[SIZEN];
LL badd[SIZEN];//整个区间被加了多少
LL cgoal[SIZEN];//跳出块之前最后跳到哪里
LL cnum[SIZEN];//跳出块之前有多少个
LL csum[SIZEN];//跳出块之前的和(不计badd)
void calc_block(int k){
	for(int i=start[k];i<=end[k];i++) lis_val[i]+=badd[k];
	badd[k]=0;
	for(int i=start[k];i<=end[k];i++){
		int j=lis_fa[i];
		if(belong[j]!=k){
			cgoal[i]=i;
			cnum[i]=1;
			csum[i]=lis_val[i];
		}
		else{
			cgoal[i]=cgoal[j];
			cnum[i]=cnum[j]+1;
			csum[i]=csum[j]+lis_val[i];
		}
	}
}
void seg_add(int l,int r,LL w){
	if(belong[l]==belong[r]){
		for(int i=l;i<=r;i++){
			lis_val[i]+=w;
		}
		calc_block(belong[l]);
	}
	else{
		for(int k=belong[l]+1;k<belong[r];k++){
			badd[k]+=w;
		}
		for(int i=l;i<=end[belong[l]];i++) lis_val[i]+=w;
		for(int i=start[belong[r]];i<=r;i++) lis_val[i]+=w;
		calc_block(belong[l]);
		calc_block(belong[r]);
	}
}
LL query(int u){
	int k=dfn[u];
	LL ans=0;
	while(k){
		ans+=csum[k]+cnum[k]*badd[belong[k]];
		k=lis_fa[cgoal[k]];
	}
	return ans;
}
void work(void){
	int cmd;
	int x,a;
	for(int i=1;i<=M;i++){
		scanf("%d",&cmd);
		if(cmd==1){
			scanf("%d%d",&x,&a);
			seg_add(dfn[x],dfn[x],a);
		}
		else if(cmd==2){
			scanf("%d%d",&x,&a);
			seg_add(dfn[x],dfn[x]+subsz[x]-1,a);
		}
		else if(cmd==3){
			scanf("%d",&x);
			LL ans=query(x);
			printf("%lld\n",ans);
		}
	}
}
void make_block(void){
	for(int i=1;i<=N;i++){
		lis_val[dfn[i]]=val[i];
		lis_fa[dfn[i]]=dfn[father[i]];
	}
	Bsize=sqrt(1.0*N)+1;
	BN=1;start[1]=1;
	int tot=0;
	for(int i=1;i<=N;i++){
		belong[i]=BN;
		end[BN]=i;
		tot++;
		if(tot>=Bsize||i==N){
			BN++;
			start[BN]=i+1;
			tot=0;
		}
	}
	for(int i=1;i<=BN;i++) calc_block(i);
}
void DFS(int x){
	dfn[x]=++timer;
	dfslis[timer]=x;
	subsz[x]=1;
	for(int i=head[x];i!=-1;i=edges[i].nxt){
		Edge &e=edges[i];
		int u=e.to;
		if(u==father[x]) continue;
		father[u]=x;
		DFS(u);
		subsz[x]+=subsz[u];
	}
}
void addedge(int from,int to){
	edges[tot]=(Edge){to,head[from]};
	head[from]=tot;
	tot++;
}
void read(void){
	scanf("%d%d",&N,&M);
	int x;
	for(int i=1;i<=N;i++){
		scanf("%d",&x);
		val[i]=x;
	}
	int a,b;
	for(int i=1;i<N;i++){
		scanf("%d%d",&a,&b);
		addedge(a,b);
		addedge(b,a);
	}
}
int main(){
	freopen("haoi2015_t2.in","r",stdin);
	freopen("haoi2015_t2.out","w",stdout);
	memset(head,-1,sizeof(head));
	read();
	DFS(1);
	make_block();
	work();
	return 0;
}