https://www.luogu.com.cn/problem/P3384

#include<bits/stdc++.h>
using namespace std;
#define lc now<<1
#define rc now<<1|1
const int M=1e5+5;
struct dian {
	int l,r,sum,add;
} f[M<<2|1];
vector<int>p[M];
int a[M],w[M],mod,top[M],size[M],fa[M],son[M],dep[M],id[M];
void pushup(int now) {
	f[now].sum=(f[lc].sum+f[rc].sum)%mod;
}
void build(int now,int l,int r) {
	f[now]= {l,r,a[l],0};
	if(l==r)return ;
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(now);
}
void pushdown(int now) {
	if(f[now].add) {
		f[lc].sum+=(f[lc].r-f[lc].l+1)*f[now].add;
		f[rc].sum+=(f[rc].r-f[rc].l+1)*f[now].add;
		f[rc].sum%=mod;
		f[lc].sum%=mod;
		f[lc].add+=f[now].add;
		f[rc].add+=f[now].add;
		f[now].add=0;
	}
}
void modi(int now,int x,int y,int k) {
	if(x<=f[now].l&&y>=f[now].r) {
		f[now].sum+=(f[now].r-f[now].l+1)*k;
		f[now].sum%=mod;
		f[now].add+=k;
		return;
	}
	pushdown(now);
	int mid=f[now].l+f[now].r>>1;
	if(x<=mid)modi(lc,x,y,k);
	if(y>mid)modi(rc,x,y,k);
	pushup(now);
}
int que(int now,int x,int y) {
	if(x<=f[now].l&&y>=f[now].r)
		return f[now].sum;
	int mid=f[now].l+f[now].r>>1;
	pushdown(now);
	int sum=0;
	if(x<=mid)sum+=que(lc,x,y);
	sum%=mod;
	if(y>mid)sum+=que(rc,x,y);
	return sum%mod;
}
void dfs1(int now,int f) {
	dep[now]=dep[f]+1,fa[now]=f,size[now]=1;
	for(auto to:p[now]) {
		if(to==f)continue;
		dfs1(to,now);
		size[now]+=size[to];
		if(size[to]>size[son[now]])son[now]=to;
	}
}
int cnt=0;
void dfs2(int now,int t) {
	id[now]=++cnt;
	a[cnt]=w[now];
	top[now]=t;
	if(!son[now])return;
	dfs2(son[now],t);
	for(int to:p[now]) {
		if(to==fa[now]||to==son[now])continue;
		dfs2(to,to);
	}
}
void fun1(int u,int v,int k) {
	while(top[u]!=top[v]) {
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		modi(1,id[top[u]],id[u],k);
		u=fa[top[u]];
	}
	if(dep[u]<dep[v])swap(u,v);
	modi(1,id[v],id[u],k);
}
int fun2(int u,int v) {
	int ans=0;
	while(top[u]!=top[v]) {
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		ans+=que(1,id[top[u]],id[u]);
		ans%=mod;
		u=fa[top[u]];
	}
	if(dep[u]<dep[v])swap(u,v);
	ans+=que(1,id[v],id[u]);
	return ans%mod;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0);
	int n,m,s;
	cin>>n>>m>>s>>mod;
	for(int i=1; i<=n; ++i)
		cin>>w[i];
	for(int i=1; i<n; ++i) {
		int x,y;
		cin>>x>>y;
		p[x].push_back(y),p[y].push_back(x);
	}
	dfs1(s,s);
	dfs2(s,s);
	build(1,1,n);
	while(m--) {
		int op,x,y,k;
		cin>>op;
		if(op==1) {
			cin>>x>>y>>k;
			fun1(x,y,k);
		} else if(op==2) {
			cin>>x>>y;
			cout<<fun2(x,y)%mod<<'\n';
		} else if(op==3) {
			cin>>x>>k;
			modi(1,id[x],id[x]+size[x]-1,k);
		} else {
			cin>>x;
			cout<<que(1,id[x],id[x]+size[x]-1)%mod<<'\n';
		}
	}
	return 0;
}