P3178 [HAOI2015]树上操作

WA50分555555

#include<bits/stdc++.h>
using namespace std;
struct node{int to,next;};node bian[200010];
int n,m,r,q,cnt;long long a[100010],head[200010],tree[100010*4],lazy[100010*4];
long long fath[100010],dep[100010],size[100010],son[100010];
long long top[100010],seg[100010],rev[100010],ans,w;
void add(int x,int y){
	cnt++;
	bian[cnt].to=y;
	bian[cnt].next=head[x];
	head[x]=cnt;
}
void build(int k,int l,int r){
	if(l==r){
		tree[k]=a[rev[l]];
		return ;
	}
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	tree[k]=tree[k*2]+tree[k*2+1]; 
}
void addp(int k,int l,int r,int v){//修改辅助 
	lazy[k]+=v;
	tree[k]+=(r-l+1)*v;
}
void down(int k,int l,int r){
	int mid=(l+r)/2;
	addp(k*2,l,mid,lazy[k]);
	addp(k*2+1,mid+1,r,lazy[k]);
	lazy[k]=0; 
}
void change(int k,int l,int r,int x,int y,int z){
	if(l>y||r<x)return ;
	if(l>=x&&r<=y)return addp(k,l,r,z);
	if(lazy[k])down(k,l,r);
	int mid=(l+r)/2;
	change(k*2,l,mid,x,y,z);
	change(k*2+1,mid+1,r,x,y,z);
	tree[k]=tree[k*2]+tree[k*2+1];
}
long long query(int k,int l,int r,int x,int y){
	if(l>y||r<x)return 0;
	if(l>=x&&r<=y)return tree[k];
	if(lazy[k])down(k,l,r);
	int mid=(l+r)/2;
	return query(k*2,l,mid,x,y)+query(k*2+1,mid+1,r,x,y);
}
void dfs1(int r,int x){
	fath[x]=r;
	dep[x]=dep[r]+1;
	size[x]=1;
	for(int k=head[x];k;k=bian[k].next){
		if(bian[k].to!=r){
			dfs1(x,bian[k].to);
			size[x]+=size[bian[k].to];
			if(size[bian[k].to]>size[son[x]])son[x]=bian[k].to;
		} 
	}
}
void dfs2(int x){
	if(son[x]){
		top[son[x]]=top[x];
		seg[son[x]]=++seg[0];
		rev[seg[son[x]]]=son[x];
		dfs2(son[x]);
	}
	for(int k=head[x];k;k=bian[k].next){
		if(!top[bian[k].to]){
			top[bian[k].to]=bian[k].to;
			seg[bian[k].to]=++seg[0];
			rev[seg[bian[k].to]]=bian[k].to;
			dfs2(bian[k].to); 
		}
	}
}
void check(int x,int y){//树上两点之间修改查询 
	int tx=top[x],ty=top[y];
	while(tx!=ty){
		if(dep[tx]<dep[ty])
			swap(x,y),swap(tx,ty);
		ans+=query(1,1,seg[0],seg[tx],seg[x]);//操作2查询 
		x=fath[tx],tx=top[x];
	}
	if(dep[x]>dep[y])swap(x,y);
	ans+=query(1,1,seg[0],seg[x],seg[y]);//操作2查询 
}
int main(){
	cin>>n>>m;r=1;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	for(int i=1;i<=n-1;i++){
		int x,y;cin>>x>>y;
		add(x,y);add(y,x);
	}
	dfs1(0,r);
	top[r]=r;seg[r]=++seg[0];rev[1]=r;
	dfs2(r); 
	build(1,1,seg[0]);	
	for(int i=1;i<=m;i++){
		int x;cin>>q;
		if(q==1){
			cin>>x>>w;
			change(1,1,seg[0],seg[x],seg[x],w);
		}
		if(q==2){
			cin>>x>>w;
			change(1,1,seg[0],seg[x],seg[x]+size[x]-1,w);
		}
		if(q==3){
			cin>>x;ans=0;
			check(x,1);cout<<ans<<endl;
		}
	}
	return 0;
}