rt，998244353年前写的树链剖分板子，不知道错哪了，能过样例，但是只有20pts

#include<bits/stdc++.h>
#define ll __int128
using namespace std;
const int N=100010;
int n,m,s;
ll p;
int h[N],e[N*2],ne[N*2],idx;
void add_edge(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int w[N],id[N];
ll seq[N],cnt;
int dep[N],sz[N],top[N],fa[N],wson[N];
ll sum[N*4],lazy[N*4]; 
inline ll read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0' or c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while('0'<=c and c<='9'){
		x=(x<<1)+(x<<3)+c-48;
		c=getchar(); 
	}
	return x;
}
void dfs1(int u,int f,int d){
	dep[u]=d,fa[u]=f,sz[u]=1;
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(v==f)continue;
		dfs1(v,u,d+1);
		sz[u]+=sz[v];
		if(sz[v]>sz[wson[u]])wson[u]=v;
	}
}
void dfs2(int u,int t){
	id[u]=++cnt;
	seq[cnt]=w[u],top[u]=t;
	if(!wson[u])return;
	dfs2(wson[u],t);
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(v==fa[u] or v==wson[u])continue;
		dfs2(v,v);
	}
}
void build(int l,int r,int index){
	lazy[index]=0;
	if(l==r){sum[index]=seq[l];return;}
	int mid=(l+r)>>1;
	build(l,mid,index*2);
	build(mid+1,r,index*2+1);
	sum[index]=sum[index*2]+sum[index*2+1];
	return;
}
void change(int l,int r,int x,int y,int index,ll v){
	if(x<=l and r<=y){
		lazy[index]+=v;
		sum[index]+=v*(r-l+1);
		return;
	}
	int mid=(l+r)>>1;
	if(lazy[index]){
		change(l,mid,1,n,index*2,lazy[index]);
		change(mid+1,r,1,n,index*2+1,lazy[index]);
		lazy[index]=0;
	}
	if(x<=mid)change(l,mid,x,y,index*2,v);
	if(mid+1<=y)change(mid+1,r,x,y,index*2+1,v);
}
ll query(int l,int r,int x,int y,int index){
	if(x<=l and r<=y)return sum[index];
	int mid=(l+r)>>1;
	if(lazy[index]){
		change(l,mid,1,n,index*2,lazy[index]);
		change(mid+1,r,1,n,index*2+1,lazy[index]);
		lazy[index]=0;
	}
	ll res=0;
	if(x<=mid)res+=query(l,mid,x,y,index*2);
	if(mid+1<=y)res+=query(mid+1,r,x,y,index*2+1);
	return res;
}
void update_pat(int u,int v,int k){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		change(1,n,/*l*/id[top[u]],/*r*/id[u],1,k);
		u=fa[top[u]];
	}
	if(dep[u]<dep[u])swap(u,v);
	change(1,n,id[v],id[u],1,k);
}
void update_tre(int u,int k){change(1,n,id[u],id[u]+sz[u]-1,1,k);}
ll query_pat(int u,int v){
	ll res=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		res+=query(1,n,/*l*/id[top[u]],/*r*/id[u],1);
		u=fa[top[u]];
	}
	if(dep[u]<dep[u])swap(u,v);
	res+=query(1,n,id[v],id[u],1);
	return res;
}
ll query_tre(int u){return query(1,n,id[u],id[u]+sz[u]-1,1);}
int main(){
	memset(h,-1,sizeof h);
	n=read(),m=read(),s=read(),p=read();
	for(int i=1;i<=n;i++)w[i]=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add_edge(u,v);
		add_edge(v,u);
	}
	dfs1(s,-1,1);
	dfs2(s,s);
	build(1,n,1); 
	while(m--){
		int op=read();
		int u,v,k;
		if(op==1){
			u=read(),v=read(),k=read();
			update_pat(u,v,k);
		}
		if(op==3){
			u=read(),k=read();
			update_tre(u,k);
		}
		if(op==2){
			u=read(),v=read();
			cout<<(long long)(query_pat(u,v)%p)<<endl;
		}
		if(op==4){
			u=read();
			cout<<(long long)(query_tre(u)%p)<<endl; 
		}
	}
}
/*
8 10 2 448348
458 718 447 857 633 264 238 944 
1 2
2 3
3 4
6 2
1 5
5 7
8 6
3 7 611
4 6
3 1 267
3 2 111
1 6 3 153
3 7 673
4 8
2 6 1
4 7
3 4 228


1208
1055
2346
1900
输出错误的样例
*/