记录编号	459076	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上操作	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	1.189 s
提交时间	2017-10-12 16:04:36	内存使用	14.42 MiB

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
vector<int>p[maxn];
int n,m,tot,fa[maxn],dep[maxn],son[maxn],siz[maxn],idx[maxn],top[maxn],end[maxn],rank[maxn];//top用来记录链首，end用来记录链尾
long long w[maxn];
struct tree{
	int l,r;
	long long sum,lazy;
}tr[maxn*4];
void dfs1(int x){
	siz[x]=1;
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i];
		if(u==fa[x])continue;
		dep[u]=dep[x]+1,fa[u]=x;
		dfs1(u);
		siz[x]+=siz[u];
		if(!son[x]||siz[u]>siz[son[x]])son[x]=u;
	}
}
void dfs2(int x,int y){
	top[x]=y,end[x]=idx[x]=++tot,rank[idx[x]]=x;
	if(!son[x])return;
	dfs2(son[x],y),end[x]=max(end[x],end[son[x]]);
	for(int i=0;i<(int)p[x].size();i++){
		int u=p[x][i];
		if(u!=fa[x]&&u!=son[x])dfs2(u,u),end[x]=max(end[x],end[u]);
	}
}
void addin(int x,int l,int r,long long c);
void updata(int x){
	tr[x].sum=tr[x<<1].sum+tr[x<<1^1].sum;
}
void downdata(int x){
	if(tr[x].lazy){
		tr[x<<1].lazy+=tr[x].lazy,tr[x<<1^1].lazy+=tr[x].lazy;
		tr[x<<1].sum+=(tr[x<<1].r-tr[x<<1].l+1)*tr[x].lazy;
		tr[x<<1^1].sum+=(tr[x<<1^1].r-tr[x<<1^1].l+1)*tr[x].lazy;
		tr[x].lazy=0;
	}
}
void buildtree(int x,int l,int r){
	tr[x].l=l,tr[x].r=r,tr[x].lazy=0;
	if(l==r)tr[x].sum=w[rank[l]];
	else{
		int mid=(l+r)>>1;
		buildtree(x<<1,l,mid);
		buildtree(x<<1^1,mid+1,r);
		updata(x);
	}
}
void addin(int x,int l,int r,long long c){
	if(l<=tr[x].l&&tr[x].r<=r)
		tr[x].lazy+=c,tr[x].sum+=(tr[x].r-tr[x].l+1)*c;
	else{
		downdata(x);
		if(l<=tr[x<<1].r)addin(x<<1,l,r,c);
		if(tr[x<<1^1].l<=r)addin(x<<1^1,l,r,c);
		updata(x);
	}
}
long long query(int x,int l,int r){
	if(l<=tr[x].l&&tr[x].r<=r)return tr[x].sum;
	else{
		long long ans=0;
		downdata(x);
		if(l<=tr[x<<1].r)ans+=query(x<<1,l,r);
		if(tr[x<<1^1].l<=r)ans+=query(x<<1^1,l,r);
		//updata(x);
		return ans;
	}
}
long long findquery(int x,int y){
	int f1=top[x],f2=top[y];
	long long ans=0;
	while(f1!=f2){
		if(dep[f1]<dep[f2])swap(f1,f2),swap(x,y);
		ans+=query(1,idx[f1],idx[x]);
		x=fa[f1],f1=top[x];
	}
	ans+=(dep[x]>dep[y])?query(1,idx[y],idx[x]):query(1,idx[x],idx[y]);
	return ans;
}
int main(){
	freopen("haoi2015_t2.in","r",stdin);
	freopen("haoi2015_t2.out","w",stdout);
	scanf("%d%d",&n,&m);
	int v,u,t;
	for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
	for(int i=1;i<n;i++)scanf("%d%d",&u,&v),p[u].push_back(v),p[v].push_back(u);
	dfs1(1),dfs2(1,1);
	buildtree(1,1,n);
	while(m--){
		scanf("%d",&t);
		if(t==1){
			scanf("%d%d",&u,&v);
			addin(1,idx[u],idx[u],v);
		}
		if(t==2){
			scanf("%d%d",&u,&v);
			addin(1,idx[u],end[u],v);
		}
		if(t==3){
			scanf("%d",&u);
			long long ans=0;
			ans=findquery(1,u);
			printf("%lld\n",ans);
		}
	}
	return 0;
}