马蜂清爽

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,r,p,u,v,op,k,cnt;
int a[100001],fa[100001],dep[100001],siz[100001],w[100001];
int top[100001],dfn[100001];
int sum[1000001],tag[1000001];
vector<int> e[100001];
void dfs1(int u){
	siz[u]=1;
	dfn[u]=++cnt;
	w[cnt]=a[u];
	for (int v:e[u]){
		if (v==fa[u]){
			continue;
		}
		dep[v]=dep[u]+1;
		fa[v]=u;
		dfs1(v);
		siz[u]+=siz[v];
	}
}
void dfs2(int u,int t){
	int p=0;
	top[u]=t;
	for (int v:e[u]){
		if (v==fa[u]){
			continue;
		}
		if (siz[v]>siz[p]){
			p=v;
		}
	}
	if (!p){
		return;
	}
	dfs2(p,t);
	for (int v:e[u]){
		if (v==fa[u]||v==p){
			continue;
		}
		dfs2(v,v);
	}
}
void pushdown(int l,int r,int mid,int k){
	tag[k<<1]+=tag[k];
	tag[k<<1|1]+=tag[k];
	sum[k<<1]+=tag[k]*(mid-l+1);
	sum[k<<1|1]+=tag[k]*(r-mid);
	tag[k<<1]%=p;
	tag[k<<1|1]%=p;
	sum[k<<1]%=p;
	sum[k<<1|1]%=p;
	tag[k]=0;
}
void modify(int l,int r,int k,int a,int b,int m){
	if (r<a||l>b){
		return;
	}
	if (l>=a&&r<=b){
		tag[k]+=m;
		sum[k]+=m*(r-l+1);
		tag[k]%=p;
		sum[k]%=p;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(l,r,mid,k);
	modify(l,mid,k<<1,a,b,m);
	modify(mid+1,r,k<<1|1,a,b,m);
	sum[k]=(sum[k<<1]+sum[k<<1|1])%p;
}
int query(int l,int r,int k,int a,int b){
	if (l>b||r<a){
		return 0;
	}
	if (l>=a&&r<=b){
		return sum[k];
	}
	int mid=(l+r)>>1;
	pushdown(l,r,mid,k);
	return (query(l,mid,k<<1,a,b)+query(mid+1,r,k<<1|1,a,b))%p;
}
void build(int l,int r,int k){
	if (l==r){
		sum[k]=w[l]%p;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,k<<1);
	build(mid+1,r,k<<1|1);
	sum[k]=(sum[k<<1]+sum[k<<1|1])%p;
}
void add(int u,int v,int k){
	while (top[u]!=top[v]){
		if (dep[v]>dep[u]){
			swap(u,v);
		}
		modify(1,n,1,dfn[top[u]],dfn[u],k);
		u=fa[top[u]];
	}
	if (dep[v]>dep[u]){
		swap(u,v);
	}
	modify(1,n,1,dfn[v],dfn[u],k);
}
int qry(int u,int v){
	int ans=0;
	while (top[u]!=top[v]){
		if (dep[v]>dep[u]){
			swap(u,v);
		}
		ans=(ans+query(1,n,1,dfn[top[u]],dfn[u]))%p;
		u=fa[top[u]];
	}
	if (dep[v]>dep[u]){
		swap(u,v);
	}
	ans=(ans+query(1,n,1,dfn[v],dfn[u]))%p;
	return ans;
}
signed main(){
	cin>>n>>m>>r>>p;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	for (int i=1;i<n;i++){
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs1(r);
	dfs2(r,r);
	build(1,n,1);
	while (m--){
		cin>>op>>u;
		if (op==1){
			cin>>v>>k;
			add(u,v,k);
		}else if (op==2){
			cin>>v;
			cout<<qry(u,v)<<endl;
		}else if (op==3){
			cin>>k;
			modify(1,n,1,dfn[u],dfn[u]+siz[u]-1,k);
		}else{
			cout<<query(1,n,1,dfn[u],dfn[u]+siz[u]-1)<<endl;
		}
	}
	return 0;
}