求助树链剖分，改自闭了

#include<bits/stdc++.h>
using namespace std;  
inline int read(){
	int x=0; char ch=getchar();
	while(ch<'0'||ch>'9') { ch=getchar(); }
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x;
}	
inline int max(const int x,const int y) { return x>y?x:y; }
inline int min(const int x,const int y) { return x<y?x:y; }
const int maxn=1e5+5;
int n,m,r,mod;
int c[maxn];
int cnt_edge=0,a[maxn<<1],nxt[maxn<<1],head[maxn];
int fa[maxn],dep[maxn],siz[maxn],hs[maxn];
int top[maxn],cnt_clock=0,mc[maxn],id[maxn];
int tag[maxn<<2],sum[maxn<<2];
inline void addline(const int x,const int y){
	a[++cnt_edge]=y,nxt[cnt_edge]=head[x],head[x]=cnt_edge;
}
inline void push_up(const int i){
	sum[i]=(sum[i<<1]+sum[i<<1|1])%mod;
}
inline void push_down(const int i,const int len){
	if(tag[i]){
		sum[i<<1]=(sum[i<<1]+(len-(len>>1))*tag[i])%mod;
		sum[i<<1|1]=(sum[i<<1|1]+(len>>1)*tag[i])%mod;
		tag[i<<1]=(tag[i<<1]+tag[i])%mod;
		tag[i<<1|1]=(tag[i<<1|1]+tag[i])%mod;
		tag[i]=0;
	}
}
void update(const int i,const int l,const int r,const int L,const int R,const int k){
	if(L<=l&&r<=R) {
		sum[i]=sum[i]+(r-l+1)*k;
		tag[i]=tag[i]+k;
		return ;
	}
	push_down(i,r-l+1);
	int mid=l+r>>1;
	if(L<=mid) update(i<<1,l,mid,L,R,k);
	if(R>mid) update(i<<1|1,mid+1,r,L,R,k);
	push_up(i);
}
int query(const int i,const int l,const int r,const int L,const int R){
	if(L<=l&&r<=R) {
		return sum[i]%mod;
	}
	push_down(i,r-l+1);
	int mid=l+r>>1,res=0;
	if(L<=mid) res+=(res+query(i<<1,l,mid,L,R))%mod;
	if(R>mid) res+=(res+query(i<<1|1,mid+1,r,L,R))%mod;
	return res;
}
void build(const int i,const int l,const int r){
	if(l==r){
		sum[i]=mc[l]%mod;
		return ;
	}
	int mid=l+r>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	push_up(i);
}
void dfs1(int u,int pre){
	fa[u]=pre,dep[u]=dep[pre]+1,siz[u]=1;
	for(register int p=head[u];p;p=nxt[p]){
		int v=a[p];
		if(v==pre) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[hs[u]]) hs[u]=v;
	}
}
void dfs2(int u,int tf){
	top[u]=tf,id[u]=++cnt_clock,mc[cnt_clock]=c[u];
	if(!hs[u]) return ;
	dfs2(hs[u],tf);
	for(register int p=head[u];p;p=nxt[p]){
		int v=a[p];
		if(v==fa[u]||v==hs[u]) continue;
		dfs2(v,v);
	}
}
inline void updson(int x,int k){
	update(1,1,n,id[x],id[x]+siz[x]-1,k);
}
inline int qson(int x){
	return query(1,1,n,id[x],id[x]+siz[x]-1);
}
inline void updrange(int x,int y,int k){
	k%=mod;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		update(1,1,n,id[top[x]],id[x],k);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	update(1,1,n,id[x],id[y],k);
} 
inline int qrange(int x,int y){
	int res=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		res=(res+query(1,1,n,id[top[x]],id[x]))%mod;
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	res=(res+query(1,1,n,id[x],id[y]))%mod;
	return res;
} 
signed main(void){
	n=read(),m=read(),r=read(),mod=read();
	for(int i=1;i<=n;++i) c[i]=read();
	for(int i=1;i<n;++i){
		int u=read(),v=read();
		addline(u,v),addline(v,u);
	}
	dfs1(r,0);
	dfs2(r,r);
	build(1,1,n);
//	for(int i=1;i<=n;++i)
//    	cout<<c[i]<<' '<<fa[i]<<' '<<dep[i]<<' '<<siz[i]<<' '<<hs[i]<<' '<<id[i]<<' '<<mc[i]<<' '<<top[i]<<' '<<endl;
	for(int i=1;i<=m;++i){
		int flag=read();
		if(flag==1){
			int x=read(),y=read(),z=read();
			updrange(x,y,z);
		}
		else if(flag==2){
			int x=read(),y=read();
			printf("%lld\n", qrange(x,y));
		}
		else if(flag==3){
			int x=read(),z=read();
			updson(x,z);
		}
		else if(flag==4){
			int x=read();
			printf("%lld\n", qson(x));
		}
	}
	return 0;
}