【代码仓库】【模板】树链剖分

#include <bits/stdc++.h>

#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define pre(i, a, b) for(int i = (a); i >= (b); i--)
#define Ede(i, u) for(int i = h[u]; i; i = ne[i])
#define go(i, a) for(auto i : a)
//#define int long long
#define uint unsigned int
#define LL long long
#define ULL unsigned long long
#define PII pair<int, int>
#define PIL pair<int, long long>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define mp make_pair
#define eb emplace_back
#define opb pop_back
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define sf scanf
#define prf printf
#define el putchar('\n')
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define mmc(arr1, arr2) memcpy(arr1, arr2, sizeof(arr2))
#define Db(x) prf("test(%s): ", x)
const int inf = 0x3f3f3f3f;

template <typename T> inline void rd(T &x){
	x = 0; bool f = true; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = false; ch = getchar();}
	while(ch >= '0' && ch <= '9'){ x = (x << 1) + (x << 3) + (ch ^ '0'); ch = getchar();}
	if(!f) x = -x;
}
template <typename T, typename ...Args> inline void rd(T &x, Args &...args){ rd(x); rd(args...);}
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
using namespace std;

const int N = 2e5 + 10, M = N << 1;
int n, m, root, mod;
int h[N], e[M], ne[M], idx;
void add(int a, int b){
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}
int Num[N << 2], tag[N << 2];
int /*dfds1*/fa[N], dep[N], siz[N], wson[N],/*dfs2*/ id[N], cnt, top[N];
LL res;
//---
void pushup(int p){
	Num[p] = Num[ls(p)] + Num[rs(p)];
}
void addtag(int p, int l, int r, int t){
	Num[p] += (r - l + 1) * t;
	Num[p] %= mod;
	tag[p] += t;
}
void pushdown(int p, int l, int r){
	if(!tag[p]) return;
	int t = tag[p];
	int mid = (l + r) >> 1;
	addtag(ls(p), l, mid, t);
	addtag(rs(p), mid + 1, r, t);
	tag[p] = 0;
}
int a[N]/*real*/, at[N]/*input, a's teamp*/;
void build(int p, int l, int r){
	if(l == r){
		Num[p] = a[l] % mod;
		return;	
	}
	int mid = (l + r) >> 1;
	build(ls(p), l, mid);
	build(rs(p), mid + 1, r);
	pushup(p);
}
void modify(int p, int l, int r, int ql, int qr, int t){
	if(ql <= l && r <= qr){
		addtag(p, l, r, t);
		return;
	}
	int mid = (l + r) >> 1;
	pushdown(p, l, r);
	if(ql <= mid) modify(ls(p), l, mid, ql, qr, t);
	if(mid <  qr) modify(rs(p), mid + 1, r, ql, qr, t);
	pushup(p);
}
void query(int p, int l, int r, int ql, int qr){
	if(ql <= l && r <= qr){
		res = (res + Num[p]) % mod;
		return;
	}
	int mid = (l + r) >> 1;
	pushdown(p, l, r);
	if(ql <= mid) query(ls(p), l, mid, ql, qr);
	if(mid <  qr) query(rs(p), mid + 1, r, ql, qr);
}
//---
void dfs1(int u, int f){ //fa, dep, siz, wson
	dep[u] = dep[f] + 1, fa[u] = f;
	siz[u] = 1;
	int maxson = 0;
	Ede(i, u){
		int v = e[i];
		if(v == f) continue;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > maxson){
			maxson = siz[v];
			wson[u] = v;
		}
	}
}
void dfs2(int u, int tp){
	id[u] = ++cnt, a[cnt] = at[u]/*in->seg*/;
	top[u] = tp;
	if(!wson[u]) return;
	dfs2(wson[u], tp);
	Ede(i, u){
		int v = e[i];
		if(v == fa[u] || v == wson[u]) continue;
		dfs2(v, v);
	}
}
//---
void mrange(int x, int y, int t){
	while(top[x] != top[y]){
		if(dep[top[x]] > dep[top[y]]) swap(x, y);
		modify(1, 1, n, id[top[y]], id[y], t);
		y = fa[top[y]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	modify(1, 1, n, id[x], id[y], t); 
}
int qrange(int x, int y){
	LL ans = 0;
	while(top[x] != top[y]){
		if(dep[top[x]] > dep[top[y]]) swap(x, y);
		res = 0, query(1, 1, n, id[top[y]], id[y]);
		ans = (ans + res) % mod;
		y = fa[top[y]];
	}
	if(dep[x] > dep[y]) swap(x, y);
	res = 0, query(1, 1, n, id[x], id[y]);
	ans = (ans + res) % mod;
	return ans;
}
void mson(int x, int t){
	modify(1, 1, n, id[x], id[x] + siz[x] - 1, t);
}
int qson(int x){
	int ans = 0;
	res = 0, query(1, 1, n, id[x], id[x] + siz[x] - 1);
	return ans = res;	
}
int main(){
	/*
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
	*/
	rd(n, m, root, mod);
	rep(i, 1, n) rd(at[i]);
	rep(i, 1, n-1){
		int x, y; rd(x, y);
		add(x, y), add(y, x);
	}
	dfs1(root, 0), dfs2(root, root);
	build(1, 1, n);
	rep(i, 1, m){
		int op; rd(op);
		int x, y, z;
		if(op == 1){
			rd(x, y, z); z %= mod;
			mrange(x, y, z);
		}else if(op == 2){
			rd(x, y);
			prf("%d\n", qrange(x, y));
		}else if(op == 3){
			rd(x, z); z %= mod;
			mson(x, z);
		}else{
			rd(x);
			prf("%d\n", qson(x));
		}
	}
	return 0;
}