Wa on4求助大佬

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
int n,m;
int d[N],f[N][18],dfn[N],depth[N],tot;
vector<int> g[N];
ll val[N],ans;
int e[N],s[N];
int root=1;
struct node{
	ll ans,tag;
	int l,r;
}rt[N];
void build(int l,int r,int k){
	rt[k].l=l,rt[k].r=r,rt[k].tag=rt[k].ans=0;
	if(l==r){rt[k].ans=val[dfn[l]];return;}
	int mid=(l+r)>>1;
	build(l,mid,k<<1),build(mid+1,r,k<<1|1);
	rt[k].ans=rt[k<<1].ans +rt[k<<1|1].ans;
}
void down(int k){
	rt[k<<1].tag +=rt[k].tag;rt[k<<1|1].tag +=rt[k].tag;
	rt[k<<1].ans +=(ll)(rt[k<<1].r-rt[k<<1].l+1)*rt[k].tag;
	rt[k<<1|1].ans +=(ll)(rt[k<<1|1].r-rt[k<<1|1].l+1)*rt[k].tag;
	rt[k].tag=0;
}
void update(int l,int r,int k,ll val){
	if(l<=rt[k].l && rt[k].r<=r){
		rt[k].tag +=val;
		rt[k].ans +=(ll)(rt[k].r-rt[k].l+1)*val;
		return;
	}
	if(rt[k].tag)down(k);
	if(r>=rt[k<<1|1].l)update(l,r,k<<1|1,val);
	if(l<=rt[k<<1].r)update(l,r,k<<1,val);
	rt[k].ans=rt[k<<1].ans+rt[k<<1|1].ans;
}
ll quer(int l,int r,int k){
	if(l<=rt[k].l && rt[k].r<=r){return rt[k].ans;}
	if(rt[k].tag)down(k);
	ll tans=0;
	if(r>=rt[k<<1|1].l)tans+=quer(l,r,k<<1|1);
	if(l<=rt[k<<1].r)tans+=quer(l,r,k<<1);
	return tans;
}
void dfs(int u,int lst){
	tot++;dfn[tot]=u;
	s[u]=tot;
	depth[u]=depth[lst]+1;
	f[u][0]=lst;
	for(int i=17;i>=1;i--)f[u][i]=f[f[u][i-1]][i-1];
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==lst)continue;
		dfs(v,u);
	}
	e[u]=tot;
}
inline int lca(int u,int v){
	if(depth[u]<depth[v])swap(u,v);
	for(int i=17;i>=0;i--)if(depth[f[u][i]]>=depth[v])u=f[u][i];
	for(int i=17;i>=0;i--)if(depth[f[u][i]]!=depth[f[v][i]])u=f[u][i],v=f[v][i];
	if(u==v)return u;
	else return f[u][0];
}
inline int dis(int u,int v){
	return depth[u]+depth[v]-2*depth[lca(u,v)];
}
inline int jum(int u,int bd){
	for(int i=17;i>=0;i--)if(depth[f[u][i]]>=bd)u=f[u][i];
	return u;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>val[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);  
	}
	dfs(1,0);
	build(1,tot,1);
	while(m--){
		int opt,u,v;
		ll x;
		cin>>opt;
		if(opt==1){
			cin>>u;
			root=u;
		}
		if(opt==2){
			cin>>u>>v>>x;
			int lcaa=lca(u,v);
			int td=(dis(root,u)+dis(root,v)-dis(u,v))/2;
			if(!td)update(s[1],e[1],1,x);
			else if(lca(lcaa,root)==lcaa){
				
				u=jum(root,depth[root]-td+1);
				//printf("all add%d  qv %d\n",1,u);
				
				update(s[1],e[1],1,x);
				update(s[u],e[u],1,-x);
			}else update(s[lcaa],e[lcaa],1,x);
		}
		if(opt==3){
			cin>>u;
			int lcaa=lca(root,u);
			if(root==u)cout<<quer(s[1],e[1],1)<<"\n";
			else
			if(lcaa==u){
				u=jum(root,depth[lcaa]+1);
			//	printf(" all %d qv %d\n",1,u);
				cout<<quer(s[1],e[1],1)-quer(s[u],e[u],1)<<"\n";
			}
			else cout<<quer(s[u],e[u],1)<<"\n";
		}
	}
	return 0;
}