评测记录，0分

树剖套线段树的做法。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,r,P;
int fst[N],nxt[N],tot,to[N];
int dep[N],f[N]; //记录每个点深度,父节点 
int siz[N],son[N]; //记录：每个点子树大小 || 重儿子 

void add_edge(int u,int v){
	nxt[++tot]=fst[u];
	fst[u]=tot;
	to[tot]=v;
}

struct tree{
	int l,r;
	int sum,lazy;
}t[8*N];

void dfs1(int p){ //处理每个点子树大小 和 重儿子 
	siz[p]=1;
	for(int i=fst[p];i;i=nxt[i]){
		int s=to[i];
		if(!dep[s]){
			dep[s]=dep[p]+1;
			f[s]=p;
			dfs1(s);
			siz[p]+=siz[s];
			if(!son[p]||siz[s]>siz[son[p]])
				son[p]=s;
		}		
	}
} 

int top[N],dfn[N],cnt; 
//top是这个点所在重链顶点编号 ，dfn是记录p节点dfn序，
int pr[N]; // 输入时的点权 
void dfs2(int p,int t){
	top[p]=t;
	dfn[p]=++cnt;
	if(!son[p]) return;
	dfs2(son[p],t);
	
	for(int i=fst[p];i;i=nxt[i])	
		if(to[i]!=son[p]&&to[i]!=f[p])
			dfs2(to[i],to[i]); 
} 

void build(int p,int l,int r){
	t[p].l=l,t[p].r=r;
	t[p].lazy=0;
	if(l==r){
		t[p].sum=pr[dfn[l]];
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}

void pushdown(int p){
	t[p<<1].lazy+=t[p].lazy , t[p<<1|1].lazy+=t[p].lazy;
	t[p<<1].sum+=t[p].lazy*(t[p<<1].r-t[p<<1].l+1); t[p<<1].sum%=P;
	t[p<<1|1].sum+=t[p].lazy*(t[p<<1|1].r-t[p<<1|1].l+1);  t[p<<1|1].sum%=P;
	t[p].lazy=0;
}

void add_sum(int p,int x,int y,int k){
	if(t[p].l>y||t[p].r<x) return;
	if(x<=t[p].l&&t[p].r<=y){
		t[p].sum+=k*(t[p].r-t[p].l+1); t[p].sum%=P;
		t[p].lazy+=k; 
		return;
	}
	if(t[p].lazy) pushdown(p);
	add_sum(p<<1,x,y,k);
	add_sum(p<<1|1,x,y,k);
	t[p].sum=t[p<<1].sum+t[p<<1|1].sum; t[p].sum%=P;
}

int pr_sum(int p,int x,int y){
	if(t[p].l>y||t[p].r<x) return 0;
	if(t[p].l>=x&&t[p].r<=y) return t[p].sum;
	if(t[p].lazy) pushdown(p);
	int ans=0;
	ans+=pr_sum(p<<1,x,y); ans%=P;
	ans+=pr_sum(p<<1|1,x,y); ans%=P;
	return ans;
}

void lca1(int u,int v,int k){
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]]){
			add_sum(1,dfn[top[u]],dfn[u],k);
			u=f[top[u]];
		}
		else{
			add_sum(1,dfn[top[v]],dfn[v],k);
			v=f[top[v]];
		}
	}
	if(dep[u]>dep[v]) swap(u,v);
	add_sum(1,dfn[u],dfn[v],k);
}

int lca2(int u,int v){
	int ans=0;
	while(top[u]!=top[v]){
		if(dep[top[u]]>dep[top[v]]){
			ans+=pr_sum(1,dfn[top[u]],dfn[u]); ans%=P;
			u=f[top[u]];
		}
		else{
			ans+=pr_sum(1,dfn[top[v]],dfn[v]); ans%=P;
			v=f[top[v]];
		}
	}
	if(dep[u]>dep[v]) swap(u,v);
	ans+=pr_sum(1,dfn[u],dfn[v]); ans%=P;
	return ans;
}

int main(){
	cin>>n>>m>>r>>P; dep[r]=1;
	for(int i=1;i<=n;i++) cin>>pr[i];
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		add_edge(x,y);
		add_edge(y,x);
	}
	dfs1(r); 
	dfs2(r,r);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int eps,x,y,z;
		cin>>eps;
		if(eps==1){
			cin>>x>>y>>z;
			lca1(x,y,z);
		}
		if(eps==2){
			cin>>x>>y;
			cout<<lca2(x,y)<<endl;
		}
		if(eps==3){
			cin>>x>>z;
			//cout<<a[x]<<" "<<a[x]+siz[x]-1<<endl;
			add_sum(1,dfn[x],dfn[x]+siz[x]-1,z);
		}
		if(eps==4){
			cin>>x;
			cout<<pr_sum(1,dfn[x],dfn[x]+siz[x]-1)<<endl;
		}
	}
	return 0;
}