比学强连通分量缩点那次萎缩的更厉害

样例没过求条

#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;

const int maxn = 1e5 + 10;
struct node {
	int l, r;
	ll sum, add;
} t[maxn << 2];
long long k;
vector<int> G[maxn];
int n, m, r, p, op, x, y, TIME, a[maxn], d[maxn], f[maxn], dfn[maxn], top[maxn], bel[maxn], siz[maxn], son[maxn];
void df(int u, int fa) {
	d[u] = f[fa] + 1;
	f[u] = fa;
	siz[u] = 1;
	for (auto v : G[u]) {
		if (v == fa) continue;
		df(v, u);
		siz[u] += siz[v];
		if (siz[son[u]] < siz[v]) son[u] = v;
	}
	return ;
}
void dfs(int u, int x) {
	dfn[u] = ++TIME;
	top[u] = x;
	bel[dfn[u]] = u;
	if (son[u]) dfs(son[u], x);
	for (auto v : G[u]) {
		if (v == f[u] || v == son[u]) continue;
		dfs(v, v);
	}
	return ;
}
void push_up(int u) {
	t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
	return ;
}
void tag(int u, ll v) {
	t[u].sum += (t[u].r - t[u].l + 1) * v;
	t[u].add += v;
	return ;
}
void push_down(int u) {
	tag(u << 1, t[u].add);
	tag(u << 1 | 1, t[u].add);
	t[u].add = 0;
	return ;
}
void build(int u, int l, int r) {
	t[u].l = l;
	t[u].r = r;
	t[u].add = 0;
	if (l == r) {
		t[u].sum = a[bel[l]];
		return ;
	}
	int mid = l + r >> 1;
	build(u << 1, l, mid);
	build(u << 1 | 1, mid + 1, r);
	push_up(u);
	return ;
}
void update(int u, int x, int y, ll k) {
	if (t[u].l >= x && t[u].r <= y) {
		tag(u, k);
		return ;
	}
	push_down(u);
	int mid = t[u].l + t[u].r >> 1;
	if (x <= mid) update(u << 1, x, y, k);
	if (y > mid) update(u << 1 | 1, x, y, k);
	push_up(u);
	return ;
}
ll query(int u, int x, int y) {
	if (x <= t[u].l && t[u].r <= y) return t[u].sum;
	ll res = 0;
	int mid = t[u].l + t[u].r >> 1;
	push_down(u);
	if (x <= mid) res += query(u << 1, x, y);
	if (y > mid) res += query(u << 1 | 1, x, y);
	return res;
}
void upd(int x, int y, ll k) {
	while (top[x] ^ top[y]) {
		if (d[top[x]] < d[top[y]]) swap(x, y);
		update(1, dfn[top[x]], dfn[x], k);
		x = f[top[x]];
	}
	if (d[x] > d[y]) swap(x, y);
	update(1, dfn[x], dfn[y], k);
	return ;
}
ll qr(int x, int y) {
	ll ans = 0;
	while (top[x] ^ top[y]) {
		if (d[top[x]] < d[top[y]]) swap(x, y);
		ans += query(1, dfn[top[x]], dfn[x]);
		x = f[top[x]];
	}
	if (d[x] > d[y]) swap(x, y);
	ans += query(1, dfn[x], dfn[y]);
	return ans;
}
int main() {
	scanf("%d %d %d %d", &n, &m, &r, &p);
	for (int i = 1; i <= n; i++) scanf("%d", a + i);
	for (int i = 1; i < n; i++) {
		scanf("%d %d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	df(r, 0);
	dfs(r, r);
	build(1, 1, n);
	while (m--) {
		scanf("%d", &op);
		if (op == 1) {
			scanf("%d %d %d", &x, &y, &k);
			upd(x, y, k);
		} else if (op == 2) {
			scanf("%d %d", &x, &y);
			printf("%lld\n", qr(x, y) % p);
		} else if (op == 3) {
			scanf("%d %d", &x, &y);
			update(1, dfn[x], dfn[x] + siz[x] - 1, k);
		} else {
			scanf("%d", &x);
			printf("%lld\n", query(1, dfn[x], dfn[x] + siz[x] - 1) % p);
		}
	}
	return 0;
}