wa on 4-10
本地跑死循环qwq

#include <iostream>
#include <algorithm>

typedef int ET;
typedef int NT;
typedef long long DT;

struct Edge
{
	ET end, next;
};

struct Node
{
	NT depth, size, father, heavyson;
	NT rank, top;
};

const int MAXN{ 100000 + 5 };
const int MAXM{ 200000 + 5 };
int MOD{};

Edge E[MAXM]{};
ET head[MAXN]{}, count{};

Node V[MAXN]{};
NT dfn[MAXN]{}, dn{};
DT value[MAXN]{}, valOrder[MAXN]{};

void addEdge(NT start, NT end)
{
	E[++count].end = end;
	E[count].next = head[start];
	head[start] = count;
}

void dfs1(NT now, NT depth)
{
	V[now].depth = depth;
	V[now].size = 1;

	for (ET i = head[now], end{}; i; i = E[i].next)
	{
		end = E[i].end;
		if (!V[end].depth)
		{
			V[end].father = now;
			dfs1(end, depth + 1);
			V[now].size += V[end].size;
			if (V[end].size > V[V[now].heavyson].size) V[now].heavyson = end;
		}
	}
}

void dfs2(NT now, NT top)
{
	V[now].top = top;
	V[now].rank = ++dn;
	dfn[dn] = now;
	valOrder[dn] = value[now];

	if (!V[now].heavyson) return;
	dfs2(V[now].heavyson, top);

	for (ET i = head[now], end{}; i; i = E[i].next)
	{
		end = E[i].end;
		if (!V[end].rank) dfs2(end, end);
	}
}

struct SN
{
	DT val, add;
};

SN tree[MAXN * 4]{};
NT n{};

inline NT mid(NT l, NT r) { return (l + r) / 2; }
inline NT len(NT l, NT r) { return (r - l + 1); }
inline NT ls(NT now) { return now * 2; }
inline NT rs(NT now) { return now * 2 + 1; }

void make_add(NT now, DT val, NT len)
{
	tree[now].val = (tree[now].val + len * val) % MOD;
	tree[now].add = (tree[now].add + val) % MOD;
}

void push_up(NT now)
{
	tree[now].val = (tree[ls(now)].val + tree[rs(now)].val) % MOD;
	//using std::cout;
	//using std::endl;
	//cout << "-----" << endl;
	//cout << now << " " << ls(now) << " " << rs(now) << endl;
	//cout << tree[now].val << " " << tree[ls(now)].val << " " << tree[rs(now)].val << endl;
}

void push_down(NT now, NT len)
{
	if (len <= 1) return;

	make_add(ls(now), tree[now].add, len - len / 2);
	make_add(rs(now), tree[now].add, len / 2);

	tree[now].add = 0;
}

// void build(NT l = 1, NT r = size)
// {
// 	NT log{};
// 	for(log = 1; log < r; log <<= 1);

// 	for (NT i{log}; i < log + r; i++) tree[i].val = value[i - log];
// 	for (NT i{log - 1}; i >= 0; i--) push_up(i);
// }

void build(NT now = 1, NT l = 1, NT r = n)
{
	if (l == r)
	{
		tree[now].val = (valOrder[l] % MOD);
		return;
	}
	NT m{mid(l, r)};
	build(ls(now), l, m);
	build(rs(now), m + 1, r);
	push_up(now);
}

void update(NT l, NT r, DT val, NT now = 1, NT cl = 1, NT cr = n)
{
	if (l <= cl && cr <= r)
	{
		make_add(now, val, len(cl, cr));
		return;
	}
	push_down(now, len(cl, cr));
	NT m{ mid(cl, cr) };
	if (l <= m) update(l, r, val, ls(now), cl, m);
	if (m < r) update(l, r, val, rs(now), m + 1, cr);
	push_up(now);
}

DT query(NT l, NT r, NT now = 1, NT cl = 1, NT cr = n)
{
	if (l <= cl && cr <= r) return tree[now].val;
	push_down(now, len(cl, cr));
	NT m{ mid(cl, cr) };
	DT ans{};
	if (l <= m) ans += query(l, r, ls(now), cl, m);
	if (m < r) ans += query(l, r, rs(now), m + 1, cr);
	return ans;
}

DT qRange(NT x, NT y)
{
	DT ans{};
	while (V[x].top != V[y].top)
	{
		if (V[V[x].top].depth < V[V[y].top].depth) std::swap(x, y);
		ans = (ans + query(V[V[x].top].rank, V[x].rank)) % MOD;
		x = V[V[x].top].father;
	}
	if (V[x].depth > V[y].depth) std::swap(x, y);
	ans += query(V[x].rank, V[y].rank);
	return ans;
}

void updRange(NT x, NT y, DT val)
{
	val %= MOD;
	while (V[x].top != V[y].top)
	{
		if (V[V[x].top].depth < V[V[y].top].depth) std::swap(x, y);
		update(V[V[x].top].rank, V[x].rank, val);
		x = V[V[x].top].father;
	}
	if (V[x].depth > V[y].depth) std::swap(x, y);
	update(V[x].rank, V[y].rank, val);
}

DT qSon(NT now)
{
	return query(V[now].rank, V[now].rank + V[now].size - 1);
}

void updSon(NT now, DT val)
{
	update(V[now].rank, V[now].rank + V[now].size - 1, val);
}

int main()
{
	using namespace std;
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int m{}, r{};
	int k{}, x{}, y{}, z{};
	cin >> n >> m >> r >> MOD;
	for (NT i = 1; i <= n; i++) cin >> value[i];
	for (ET i = 0, x{}, y{}; i < n - 1; i++)
	{
		cin >> x >> y;
		addEdge(x, y);
		addEdge(y, x);
	}
	dfs1(r, 1);
	dfs2(r, r);
	build();
	while (m--)
	{
		cin >> k;
		switch (k)
		{
		case 1:
			cin >> x >> y >> z;
			updRange(x, y, z);
			break;
		case 2:
			cin >> x >> y;
			cout << qRange(x, y) << endl;
			break;
		case 3:
			cin >> x >> y;
			updSon(x, y);
			break;
		case 4:
			cin >> x;
			cout << qSon(x) << endl;
			break;
		default:
			break;
		}
	}
}