rt，

#include <bits/stdc++.h>

using namespace std;
const int maxn = 100004;
int n, q, root;
long long mod;
struct node
{
	int depth, size, son, fa, chain;
	long long val;
};
node graph[maxn];
vector<int> to[maxn];
int vis[maxn];

void dfs1(int u)
{
	if(vis[u]) return;
	vis[u] = 1;
	graph[u].size = 1;
	for(int v : to[u])
	{
		if(vis[v]) continue;
		graph[v].depth = graph[u].depth + 1;
		graph[v].fa = u;
		dfs1(v);
		graph[u].size += graph[v].size;
		if(graph[v].size > graph[graph[u].son].size)
			graph[u].son = v; 
	}
} 

struct chn
{
	int head, depth;
};
chn chain[maxn];
vector<int> cto[maxn]; // directed
int dfn[maxn], pos[maxn];
int ccnt = 0, gcnt = 0;
void dfs2(int u)
{
	if(vis[u] || u<=0) return;
	if(graph[u].chain == 0)
	{
		chain[++ccnt].head = u;
		graph[u].chain = ccnt;
		if(ccnt != 1)
		{
			cto[graph[graph[u].fa].chain].push_back(ccnt);
			chain[ccnt].depth = chain[graph[graph[u].fa].chain].depth + 1;
		}
		else chain[ccnt].depth = 0;
	}
	vis[u] = 1;
	dfn[u] = ++gcnt; 
	pos[gcnt] = u;
	graph[graph[u].son].chain = graph[u].chain;
	dfs2(graph[u].son);
	for(int v : to[u])
	{
		if(vis[v]) continue;
		dfs2(v);
	}
}

struct nd
{
	int l, r;
	long long val, lazy;
	inline int len() { return r-l+1; }
};
nd segt[4*maxn];

inline int fa(int u) { return u>>1; }
inline int lc(int u) { return u<<1; }
inline int rc(int u) { return u<<1|1; }

void push_up(int cur)
{
	segt[cur].val = segt[lc(cur)].val + segt[rc(cur)].val;
}

void push_down(int cur)
{
	segt[lc(cur)].val += segt[lc(cur)].len() * segt[cur].lazy;
	segt[rc(cur)].val += segt[rc(cur)].len() * segt[cur].lazy;
	segt[lc(cur)].lazy += segt[cur].lazy;
	segt[rc(cur)].lazy += segt[cur].lazy;
	segt[cur].lazy = 0;
}

void build(int cur, int l, int r)
{
	segt[cur].l = l;
	segt[cur].r = r;
	if(l == r)
	{
		segt[cur].val = graph[pos[l]].val;
		// printf("build(%d, %d, %d) reached leaf: %d\tdfn=%d -> id=%d\n", cur, l, r, graph[pos[l]].val, l, pos[l]);
		return;
	}
	int mid = (l+r)/2;
	build(lc(cur), l, mid);
	build(rc(cur), mid+1, r);
	push_up(cur);
}

long long query(int cur, int l, int r)
{
	if(cur == 1 && l > r) swap(l, r);
	// printf("query(%d, %d, %d)\n", cur, l, r);
	if(segt[cur].l > r || segt[cur].r < l) return 0;
	if(l <= segt[cur].l && segt[cur].r <= r) return segt[cur].val;
	int mid = (segt[cur].l + segt[cur].r) / 2;
	long long ret = 0;
	push_down(cur);
	if(l <= mid) ret += query(lc(cur), l, r);
	if(r > mid) ret += query(rc(cur), l, r);
	return ret;
}

void update(int cur, int l, int r, long long k)
{
	if(cur == 1 && l > r) swap(l, r);
	// printf("update(%d, %d, %d, %lld)\n", cur, l, r, k);
	if(segt[cur].l > r || segt[cur].r < l) return;
	if(l <= segt[cur].l && segt[cur].r <= r)
	{
		segt[cur].val += segt[cur].len() * k;
		segt[cur].lazy += k;
		return;
	}
	int mid = (segt[cur].l + segt[cur].r) / 2;
	push_down(cur);
	if(l <= mid) update(lc(cur), l, r, k);
	if(r > mid) update(rc(cur), l, r, k);
	push_up(cur); 
}

long long query_size(int u)
{
	return query(1, dfn[u], dfn[u] + graph[u].size - 1);
}

void update_size(int u, long long k)
{
	update(1, dfn[u], dfn[u] + graph[u].size - 1, k);
} 

int lca(int u, int v)
{
	if(graph[u].chain == graph[v].chain)
	{
		if(dfn[u] < dfn[v]) return u;
		else return v;
	}
	if(chain[graph[u].chain].depth > chain[graph[v].chain].depth) return lca(graph[u].fa, v);
	else return lca(graph[v].fa, u);
}

long long query_path(int u, int v)
{
	if(graph[u].chain == graph[v].chain)
	{
		if(dfn[u] < dfn[v]) return query(1, dfn[u], dfn[v]);
		else return query(1, dfn[v], dfn[u]);
	}
	long long ret = 0;
	//if(chain[graph[u].chain].depth > chain[graph[v].chain].depth)
	if(graph[chain[graph[u].chain].head].depth > graph[chain[graph[v].chain].head].depth)
		ret += query_path(graph[u].fa, v) + query(1, dfn[u], dfn[chain[graph[u].chain].head]);
	else ret += query_path(graph[v].fa, u) + query(1, dfn[v], dfn[chain[graph[v].chain].head]);
	return ret;
}

void update_path(int u, int v, long long k)
{
	if(graph[u].chain == graph[v].chain)
	{
		if(dfn[u] < dfn[v]) update(1, dfn[u], dfn[v], k);
		else update(1, dfn[v], dfn[u], k);
		return; 
	}
	if(graph[chain[graph[u].chain].head].depth > graph[chain[graph[v].chain].head].depth)
	{
		update(1, dfn[u], dfn[chain[graph[u].chain].head], k);
		update_path(graph[u].fa, v, k);
	}
	else 
	{
		update(1, dfn[v], dfn[chain[graph[v].chain].head], k);
		update_path(graph[v].fa, u, k);
	}
}

// node的fa是它图上的父亲，son是重儿子，chain是所属的那一条链；
// chn的head是链头的节点，cto[]是以链为节点建的图

int main()
{
	scanf("%d%d%d%lld", &n, &q, &root, &mod);
	for(int i=1;i<=n;i++) scanf("%lld", &graph[i].val);
	for(int i=1;i<=n-1;i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		to[u].push_back(v);
		to[v].push_back(u);
	}
	dfs1(root);
	for(int i=0;i<=n;i++) vis[i] = 0;
	dfs2(root);
	/*
	for(int i=1;i<=n;i++)
	{
		printf("Node %d: dfn=%d, val=%d, fa=%d, son=%d, chain=%d\t\tsize=%d, depth=%d;\tpos[%d]=%d\n",
			i, dfn[i], graph[i].val, graph[i].fa, graph[i].son, graph[i].chain, graph[i].size, graph[i].depth, i, pos[i]);
	}
	printf("\n");
	for(int i=1;i<=ccnt;i++)
	{
		printf("Chain %d: head=%d, depth=%d\n",
			i, chain[i].head, chain[i].depth);
	}
	*/ 
	build(1, 1, n);
	
	// for(int i=1;i<=n;i++) printf("segt[%d].val = %d as %d in query\n", i, segt[i].val, query(1, i, i));
	// for(int i=1;i<=n;i++) printf("segt[%d].val = %d\n", i, segt[i].val);
	
	while(q--)
	{
		int opt, x, y;
		long long z;
		scanf("%d", &opt);
		if(opt == 1)
		{
			scanf("%d%d%lld", &x, &y, &z);
			update_path(x, y, z); 
		}
		if(opt == 2)
		{
			scanf("%d%d", &x, &y);
			printf("%lld\n", query_path(x, y) % mod);
		}
		if(opt == 3)
		{
			scanf("%d%lld", &x, &z);
			update_size(x, z);
		}
		if(opt == 4)
		{
			scanf("%d", &x);
			printf("%lld\n", query_size(x) % mod);
		}
		if(opt == 5)
		{
			scanf("%d%d", &x, &y);
			printf("LCA of (%d, %d) = %d\n", x, y, lca(x, y));
		}
	}
	return 0;
}

https://www.luogu.com.cn/record/194602471