代码求调

#include<bits/stdc++.h>
#define N 100100
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;
int n,m,rt,Mod,cnt;
int a[N<<2],id[N],hs[N],size[N],f[N],dep[N];
int t[N<<2],tag[N<<2],top[N],dfn[N];
vector<int>g[N];
void add(int u,int v){
	g[u].push_back(v);
	g[v].push_back(u);
}
void dfs1(int u,int fa){
	size[u]=1;
	f[u]=fa;
	dep[u]=dep[fa]+1;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa)continue;
		dfs1(v,u);
		size[u]+=size[v];
		if(size[v]>size[hs[u]])hs[u]=v;
	}
}
void dfs2(int u,int fa,int hson){
	top[u]=hson;
	dfn[u]=++cnt;
	id[cnt]=u;
	if(hs[u])dfs2(hs[u],u,hson);
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i];
		if(v==fa)continue;
		if(v==hs[u])continue;
		dfs2(v,u,v);
	}
}
void push_up(int p){t[p]=(t[ls(p)]+t[rs(p)])%Mod;}
void build(int p,int pl,int pr){
	tag[p]=0;
	if(pl==pr){t[p]=a[id[pl]];return ;}
	int mid=(pl+pr)>>1;
	build(ls(p),pl,mid);
	build(rs(p),mid+1,pr);
	push_up(p);
}
void add_tag(int p,int pl,int pr,int w){
	tag[p]=(tag[p]+w)%Mod;
	t[p]=(t[p]+(pr-pl+1)*w)%Mod;
}
void push_down(int p,int pl,int pr){
	if(!tag[p])return ;
	int mid=(pl+pr)>>1;
	add_tag(ls(p),pl,mid,tag[p]);
	add_tag(ls(p),mid+1,pr,tag[p]);
	tag[p]=0;
}
void update(int L,int R,int p,int pl,int pr,int w){
	if(L<=pl&&R>=pr){add_tag(p,pl,pr,w);return ;}
	push_down(p,pl,pr);
	int mid=(pl+pr)>>1;
	if(L<=mid)update(L,R,ls(p),pl,mid,w);
	if(R>=mid+1)update(L,R,rs(p),mid+1,pr,w);
	push_up(p);
}
void update1(int x,int y,int z){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		if(top[x]==x){
			update(dfn[x],dfn[x],1,1,n,z);
			x=f[x];
		}
		else{
			update(dfn[top[x]],dfn[x],1,1,n,z);	
			x=f[top[x]];
		}
	}
	if(dep[x]<dep[y])swap(x,y);
	update(dfn[y],dfn[x],1,1,n,z);
}
int query2(int L,int R,int p,int pl,int pr){
	if(L<=pl&&R>=pr)return t[p]%Mod;
	push_down(p,pl,pr);
	int res=0;
	int mid=(pl+pr)>>1;
	if(L<=mid)res=(res+query2(L,R,ls(p),pl,mid))%Mod;
	if(R>=mid+1)res=(res+query2(L,R,rs(p),mid+1,pr))%Mod;
	return res%Mod; 
}
int query1(int x,int y){
	int res=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		if(top[x]==x){
			res=(res+query2(dfn[x],dfn[x],1,1,n))%Mod;
			x=f[x];
		}
		else{
			res=(res+query2(dfn[top[x]],dfn[x],1,1,n))%Mod;	
			x=f[top[x]];
		}
	}
	if(dep[x]<dep[y])swap(x,y);
	return (res+query2(dfn[y],dfn[x],1,1,n))%Mod;	
}
int main()
{	
	cin>>n>>m>>rt>>Mod;
	for(int i=1;i<=n;i++)cin>>a[i],a[i]%=Mod;
	for(int i=1;i<=n-1;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	cnt=0;
	dfs1(rt,0);
	dfs2(rt,0,rt);
	build(1,1,n);
	while(m--){
		int op,x,y,z;
		cin>>op;
		if(op==1){
			cin>>x>>y>>z;
			z%=Mod;
			update1(x,y,z);
		}
		if(op==2){
			cin>>x>>y;
			cout<<query1(x,y)<<"\n";
		}
		if(op==3){
			cin>>x>>z;
			z%=Mod;
			update(dfn[x],dfn[x]+size[x]-1,1,1,n,z);
		}
		if(op==4){
			cin>>x;
			cout<<query2(dfn[x],dfn[x]+size[x]-1,1,1,n)<<"\n";
		}
	}
	return 0;
}