样例输出了

2
19

#include <bits/stdc++.h>
#define int long long
#define ls p << 1
#define rs p << 1 | 1

using namespace std;

const int N = 1e5 + 5;

int n, m, root, P, _index;

int a[N], f[N], h[N], siz[N], t[N], dfn[N], rdfn[N], d[N], tree[N], change[N];

vector <int> v[N];

void orz (int p) {
	tree[p] %= P;
	change[p] %= P;
}

void pushup (int p) {
	tree[p] = tree[ls] + tree[rs];
	orz (p);
}

void pushdown (int len, int p) {
	change[ls] += change[p];
	change[rs] += change[p];
	tree[ls] += change[p] * (len - len >> 1);
	tree[rs] += change[p] * (len >> 1);
	change[p] = 0;
	orz (p);
	orz (ls);
	orz (rs);
}

void build (int l = 1, int r = n, int p = 1) {
	if (l == r) {
		tree[p] = a[rdfn[l]];
	} else {
		int mid = (l + r) >> 1;
		build (l, mid, ls);
		build (mid + 1, r, rs);
		pushup (p);
	}
}

void update (int l, int r, int k, int cl = 1, int cr = n, int p = 1) {
	if (l > r) { swap (l, r); }
	if (cl > r || cr < l) {
		return;
	} else if (cl >= l && cr <= r) {
		tree[p] += k * (cr - cl + 1);
		change[p] += k;
	} else {
		int mid = (cl + cr) >> 1;
		pushdown (cr - cl + 1, p);
		update (l, r, k, cl, mid, ls);
		update (l, r, k, mid + 1, cr, rs);
		pushup (p);
	}
}

int query (int l, int r, int cl = 1, int cr = n, int p = 1) {
	if (l > r) { swap (l, r); }
	if (cl > r || cr < l) {
		return 0;
	} else if (cl >= l && cr <= r) {
		return tree[p];
	} else {
		int mid = (cl + cr) >> 1;
		pushdown (cr - cl + 1, p);
		return (query (l, r, cl, mid, ls) + query (l, r, mid + 1, cr, rs)) % P;
	}
}

void dfs1 (int cur, int father) {
	f[cur] = father;
	siz[cur] = 1;
	d[cur] = f[father] + 1;
	
	for (int i = 0; i < v[cur].size (); ++ i) {
		if (v[cur][i] != father) {
			dfs1 (v[cur][i], cur);
			siz[cur] += siz[v[cur][i]];
			
			if (siz[v[cur][i]] > siz[h[cur]]) { h[cur] = v[cur][i]; }
		}
	}
}

void dfs2 (int cur, int top) {
	dfn[cur] = ++ _index;
	rdfn[_index] = cur;
	t[cur] = top;
	
	if (h[cur]) {
		dfs2 (h[cur], top);
		
		for (int i = 0; i < v[cur].size (); ++ i) {
			if (v[cur][i] != f[cur] && v[cur][i] != h[cur]) {
				dfs2 (v[cur][i], v[cur][i]);
			}
		}
	}
}

void add (int x, int y, int z) {
	while (t[x] != t[y]) {
		if (d[x] < d[y]) { swap (x, y); }
		update (dfn[t[x]], dfn[x], z);
		x = f[t[x]];
	}
	
	update (dfn[x], dfn[y], z);
}

int sum (int x, int y) {
	int total = 0;
	
	while (t[x] != t[y]) {
		if (d[x] < d[y]) { swap (x, y); }
		total += query (dfn[t[x]], dfn[x]);
		total %= P;
		x = f[t[x]];
	}
	
	return total + query (dfn[x], dfn[y]);
}

signed main () {
	cin >> n >> m >> root >> P;
	
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i];
	}
	
	for (int x, y, i = 1; i < n; ++ i) {
		cin >> x >> y;
		v[x].push_back (y);
		v[y].push_back (x);
	}
	
	dfs1 (root, 0);
	
	dfs2 (root, 0);
	
	build ();
	
	for (int op, x, y, z; m; -- m) {
		cin >> op >> x;
		
		if (op == 1) {
			cin >> y >> z;
			add (x, y, z);
		} else if (op == 2) {
			cin >> y;
			cout << sum (x, y) % P << endl;
		} else if (op == 3) {
			cin >> y;
			update (dfn[x], dfn[x] + siz[x] - 1, y);
		} else {
			cout << query (dfn[x], dfn[x] + siz[x] - 1) % P << endl;
		}
	}
	
	return 0;
}