树剖板子 19pts 求调

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read(){
	ll a=0,x=1;
	char c=getchar();
	while (!isdigit(c)){
		if (c=='-')
			x=-x;
		c=getchar();
	}
	while (isdigit(c)){
		a=a*10+c-'0';
		c=getchar();
	}
	return x*a;
}
int n,c=0,hd[100001],nt[200001],to[200001],fa[100001],sn[100001],sz[100001],dh[100001],id[100001],tp[100001];
ll md,k[100001],s[400001],t[400001],wt[100001];
ll plus(ll x,ll y){
	return (x%md+y%md)%md;
}
inline int lc(int x){
	return x<<1;
}
inline int rc(int x){
	return (x<<1)|1;
}
inline void push_up(int p){
	s[p]=plus(s[lc(p)],s[rc(p)]);
	return;
}
void build(int p,int l,int r){
	int m=(l+r)>>1;
	if (l==r){
		s[p]=k[l];
		return;
	}
	build(lc(p),l,m);
	build(rc(p),m+1,r);
	push_up(p);
	return;
}
inline void f(int p,int l,int r,ll x){
	t[p]=plus(t[p],x);
	s[p]=plus(s[p],(x%p)*((r-l+1)%p)%p);
	return;
}
void push_down(int p,int l,int r){
	int m=(l+r)>>1;
	f(lc(p),l,m,t[p]);
	f(rc(p),m+1,r,t[p]);
	t[p]=0;
	return;
}
void add(int nl,int nr,int p,int l,int r,ll x){
	int m=(l+r)>>1;
	if ((nl<=l)&&(nr>=r)){
		f(p,l,r,x);
		return;
	}
	push_down(p,l,r);
	if (nl<=m)
		add(nl,nr,lc(p),l,m,x);
	if (nr>m)
		add(nl,nr,rc(p),m+1,r,x);
	push_up(p);
	return;
}
ll sum(int nl,int nr,int p,int l,int r){
	int m=(l+r)>>1;
	ll a=0;
	if ((nl<=l)&&(nr>=r))
		return s[p];
	push_down(p,l,r);
	if (nl<=m)
		a=plus(a,sum(nl,nr,lc(p),l,m));
	if (nr>m)
		a=plus(a,sum(nl,nr,rc(p),m+1,r));
	return a;
}
inline void add_edge(int x,int y){
	nt[++c]=hd[x];
	hd[x]=c;
	to[c]=y;
	nt[++c]=hd[y];
	hd[y]=c;
	to[c]=x;
	return;
}
//----------以上部分大概率没错----------
void dfs1(int x,int f,int d){
	int mx=0;
	fa[x]=f;
	dh[x]=d;
	sz[x]=1;
	for (int i=hd[x];i;i=nt[i])
		if (to[i]!=f){
			dfs1(to[i],x,d+1);
			sz[x]+=sz[to[i]];
			if (sz[to[i]]>mx){
				mx=sz[to[i]];
				sn[x]=to[i];
			}
		}
	return;
}
void dfs2(int x,int f){
	id[x]=++c;
	k[c]=wt[x];
	tp[x]=f;
	if (!sn[x])
		return;
	dfs2(sn[x],f);
	for (int i=hd[x];i;i=nt[i])
		if ((to[i]!=fa[x])&&(to[i]!=sn[x]))
			dfs2(to[i],to[i]);
	return;
}
void add1(int x,int y,ll z){
	z%=md;
	while (tp[x]!=tp[y]){
		if (dh[tp[x]]<dh[tp[y]])
			swap(x,y);
		add(id[x],id[tp[x]],1,1,n,z);
		x=fa[tp[x]];
	}
	if (dh[x]<dh[y])
		swap(x,y);
	add(id[x],id[y],1,1,n,z);
	return;
}
ll sum1(int x,int y){
	ll as=0;
	while (tp[x]!=tp[y]){
		if (dh[tp[x]]<dh[tp[y]])
			swap(x,y);
		as=plus(as,sum(id[x],id[tp[x]],1,1,n));
		x=fa[tp[x]];
	}
	if (dh[x]>dh[y])
		swap(x,y);
	as=plus(as,sum(id[x],id[y],1,1,n));
	return as%md;
}
void add2(int x,ll y){
	y%=md;
	add(id[x],id[x]+sz[x]-1,1,1,n,y);
	return;
}
ll sum2(int x){
	return sum(id[x],id[x]+sz[x]-1,1,1,n)%md;
}
signed main(){
	int m,r,u,v,o,a,b,f;
	n=read();
	m=read();
	r=read();
	md=read();
	for (int i=1;i<=n;++i)
		wt[i]=read();
	for (int i=1;i<n;++i){
		u=read();
		v=read();
		add_edge(u,v);
	}
	dfs1(r,0,1);
	c=0;
	dfs2(r,r);
	build(1,1,n);
	for (int i=1;i<=m;++i){
		o=read();
		a=read();
		if (o==1){
			b=read();
			f=read();
			add1(a,b,f);
		}
		else if (o==2){
			b=read();
			printf("%lld\n",sum1(a,b));
		}
		else if (o==3){
			b=read();
			add2(a,b);
		}
		else
			printf("%lld\n",sum2(a));
	}
	return 0;
}