P3384 树剖模版 37pts

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

#define int long long

vector<int> h[N];
int a[N], as[N], top[N], dep[N], fa[N], size[N], son[N], id[N], cnt = 0;
int mod, n, m, r;

class SegTree {
public:
#define ls(p) ((p) << 1)
#define rs(p) ((p) << 1 | 1)
#define up(p) (t[ls(p)] + t[rs(p)])%mod
#define mid (((l)+(r))>>1)
	void build(int p, int l, int r) {
		lzy[p] = 0;
		if (l == r) {
			t[p] = a[l] % mod;
			return;
		}
		build(ls(p), l, mid);
		build(rs(p), mid + 1, r);
		t[p] = up(p);
	}
	inline void f(int p, int l, int r, int k) {
		lzy[p] = lzy[p] + k;
		t[p] = (t[p] + k * (r - l + 1)) % mod;
	}
	inline void push_down(int p, int l, int r) {
		f(ls(p), l, mid, lzy[p]);
		f(rs(p), mid + 1, r, lzy[p]);
		lzy[p]=0;
	}

	inline void update(int p, int l, int r, int L, int R , int k) {
		if (L <= l && r <= R) {
			t[p] += k * (r - l + 1);
			lzy[p] += k;
		}
		else {
			if(lzy[p]) push_down(p, l, r);
			if (L <= mid) update(ls(p), l, mid, L, R, k);
			if (R > mid) update(rs(p), mid + 1, r, L, R, k);
			t[p] = up(p);
		}
	}
	inline int query(int p, int l, int r, int L, int R) {
		int res = 0;
		if (L <= l && r <= R) {
			res += t[p];
			res %= mod;
		} else {
			if(lzy[p]) push_down(p, l, r);
			if (L <= mid) res += query(ls(p), l, mid, L, R);
			if (R > mid) res += query(rs(p), mid + 1, r, L, R);
		}
		return res;
	}
private:
	int t[N << 2], lzy[N << 2];
} T;

void dfs1(int x, int f, int deep) {
	dep[x] = deep;
	fa[x] = f;
	size[x] = 1;
	int mson = -1;
	for (int i : h[x]) {
		if (i == f) continue;
		dfs1(i, x, deep + 1);
		size[x] += size[i];
		if (size[i] > mson) son[x] = i, mson = size[i];
	}
}

void dfs2(int x, int topf) {
	id[x] = ++cnt;
	a[cnt] = as[x];
	top[x] = topf;
	if (!son[x]) return;
	dfs2(son[x], topf);
	for (int i : h[x]) {
		if (i == fa[x] || i == son[x]) continue;
		dfs2(i, i);
	}
}

int qRange(int x, int y) {
	int ans = 0;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) x ^= y, y ^= x, x ^= y;
		ans += T.query(1, 1, n, id[top[x]], id[x]);
		ans %= mod;
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) x ^= y, y ^= x, x ^= y;
	ans += T.query(1, 1, n, id[x], id[y]);
	return ans % mod;
}

int qSon(int x) {
	//printf("id[%lld] = %lld\n",x,id[x]);
	return T.query(1, 1, n, id[x], id[x] + size[x] - 1);
}

void updRange(int x, int y, int k) {
	k %= mod;
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		T.update(1, 1, n, id[top[x]], id[x], k);
		x = fa[top[x]];
	}
	if (dep[x] > dep[y])swap(x, y);
	T.update(1, 1, n, id[x], id[y], k);
}

void updSon(int x, int k) {
	//printf("id[%lld] = %lld\n",x,id[x]);
	T.update(1, 1, n, id[x], id[x] + size[x] - 1, k);
}

signed main() {
	scanf("%lld%lld%lld%lld", &n, &m, &r, &mod);
	for (int i = 1; i <= n; i++) scanf("%lld", &as[i]);
	for (int i = 1; i < n; i++) {
		int a, b;
		scanf("%lld%lld", &a, &b);
		h[a].push_back(b);
		h[b].push_back(a);
	}
	dfs1(r, 0, 1);
	dfs2(r, r);
	T.build(1, 1, n);
	while (m--) {
		int op, x, y, z;
		scanf("%lld", &op);
		if (op == 1) {
			scanf("%lld%lld%lld", &x, &y, &z);
			updRange(x, y, z);
		} else if (op == 2) {
			scanf("%lld%lld", &x, &y);
			printf("%lld\n", qRange(x, y));
		} else if (op == 3) {
			scanf("%lld%lld", &x, &y);
			updSon(x, y);
		} else if (op == 4) {
			scanf("%lld", &x);
			printf("%lld\n", qSon(x));
		}
	}
	return 0;
}