测评记录：https://www.luogu.com.cn/record/55381173

#include <bits/stdc++.h>
#define reg register

using namespace std;

typedef long long LL;
const int N = 100010;

int n, m, r, P, w[N], wt[N];
int Ecnt, head[N], nxt[N * 2], ver[N * 2];
int Fa[N], son[N], dep[N], sz[N], top[N], dfn[N], dfnid; 

struct SegmentTree
{
	int l, r;
	LL sum, add;
} tree[N * 4];

inline int lson(reg int p) {return p * 2;}
inline int rson(reg int p) {return p * 2 + 1;}

void build(reg int p, reg int l, reg int r)
{
	tree[p].l = l, tree[p].r = r;
	if (l == r)
	{
		tree[p].sum = wt[l];
		return;
	}
	reg int mid = (l + r) >> 1;
	build(lson(p), l, mid);
	build(rson(p), mid + 1, r);
	tree[p].sum = (tree[lson(p)].sum + tree[rson(p)].sum) % P;
}

inline void spread(reg int p)
{
	if (tree[p].add)
	{
		tree[lson(p)].sum = (tree[lson(p)].sum + 1ll * tree[p].add * (tree[lson(p)].r - tree[lson(p)].l + 1) % P) % P;
		tree[rson(p)].sum = (tree[rson(p)].sum + 1ll * tree[p].add * (tree[rson(p)].r - tree[rson(p)].l + 1) % P) % P;
		tree[lson(p)].add += tree[p].add;
		tree[rson(p)].add += tree[p].add;
		tree[p].add = 0;
	}
}

void change(reg int p, reg int l, reg int r, reg int d)
{
	if (l <= tree[p].l && r >= tree[p].r)
	{
		tree[p].sum = (tree[p].sum + 1ll * d * (tree[p].r - tree[p].l + 1) % P) % P;
		tree[p].add += d;
		return;
	}
	spread(p);
	reg int mid = (tree[p].l + tree[p].r) / 2;
	if (l <= mid) change(lson(p), l, r, d);
	if (r > mid) change(rson(p), l, r, d);
	tree[p].sum = (tree[lson(p)].sum + tree[rson(p)].sum) % P;
}

LL ask(reg int p, reg int l, reg int r)
{
	if (l <= tree[p].l && r >= tree[p].r) return tree[p].sum;
	spread(p);
	reg int mid = (tree[p].l + tree[p].r) / 2;
	reg LL val = 0;
	if (l <= mid) val = (val + ask(lson(p), l, r)) % P;
	if (r > mid) val = (val + ask(rson(p), l, r)) % P;
	return val;
}

inline void link(reg int x, reg int y)
{
	ver[ ++ Ecnt] = y;
	nxt[Ecnt] = head[x];
	head[x] = Ecnt;
}

void dfs1(reg int x, reg int fa)
{
	Fa[x] = fa;
	sz[x] = 1;
	dep[x] = dep[fa] + 1;
	
	for (reg int i = head[x]; i; i = nxt[i])
	{
		reg int y = ver[i];
		if (y == fa) return;
		
		dfs1(y, x);
		
		sz[x] += sz[y];
		if (sz[y] > sz[son[x]]) son[x] = y;
	}
}

void dfs2(reg int x, reg int t)
{
	top[x] = t;
	dfn[x] = ++ dfnid;
	wt[dfnid] = w[x];
	if (son[x]) dfs2(son[x], t);
	
	for (reg int i = head[x]; i; i = nxt[i])
	{
		reg int y = ver[i];
		if (y != son[x] && y != Fa[x]) dfs2(y, y);
	}
}

inline void Addp(reg int x, reg int y, reg int z)
{
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		change(1, dfn[top[x]], dfn[x], z);
		x = Fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	change(1, dfn[x], dfn[y], z);
}

inline LL Askp(reg int x, reg int y)
{
	LL ans = 0;
	while (top[x] != top[y])
	{
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		ans = (ans + ask(1, dfn[top[x]], dfn[x])) % P;
		x = Fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x, y);
	ans = (ans + ask(1, dfn[x], dfn[y])) % P;
	return ans;
}

inline void Addn(reg int x, reg int z)
{
	change(1, dfn[x], dfn[x] + sz[x] - 1, z);
}

inline LL Askn(reg int x)
{
	return ask(1, dfn[x], dfn[x] + sz[x] - 1);
}

int main()
{
	scanf("%d %d %d %d", &n, &m, &r, &P);
	for (reg int i = 1; i <= n; ++ i) scanf("%d", &w[i]); 
	for (reg int i = 1; i < n; ++ i) 
	{
		reg int x, y;
		scanf("%d %d", &x, &y);
		link(x, y);
		link(y, x);
	}
	
	dfs1(r, 0);
	dfs2(r, r);
	build(1, 1, n);
	
	while (m -- )
	{
		reg int opt, x, y, z;
		scanf("%d", &opt);
		
		if (opt == 1)
		{
			scanf("%d %d %d", &x, &y, &z);
			Addp(x, y, z);
		}
		else if (opt == 2)
		{
			scanf("%d %d", &x, &y);
			printf("%lld\n", Askp(x, y));
		}
		else if (opt == 3)
		{
			scanf("%d %d", &x, &z);
			Addn(x, z);
		}
		else
		{
			scanf("%d", &x);
			printf("%lld\n", Askn(x));
		}
    }
    
    return 0;
}