37pts求调

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100100;
LL val[N], mod;
int n;
//
int tot;
struct node {
	int x, nxt;
}e[N * 2];
int  head[N];
void add(int u, int v) {
	e[++tot] = (node) {v, head[u]};
	head[u] = tot;
}
//链式前向星 
int dep[N], F[N], siz[N], ls[N], dfn[N], top[N];
LL a[N];
//
struct Lazy {
	LL add;
};
struct TR {
	LL sum;
	int len;
	Lazy t;
}tree[N * 4];
Lazy operator + (const Lazy&l, const Lazy&r) {
	return (Lazy) {(l.add + r.add) % mod};
}
void update(int id) {
	tree[id].sum = (tree[id * 2].sum + tree[id * 2 + 1].sum) % mod;
	tree[id].len = tree[id * 2].len + tree[id * 2 + 1].len;
}
void build(int id, int l, int r) {
	if(l == r) {
		tree[id] = (TR) {a[l] % mod, 1, (Lazy){0}};
		return;
	}
	int mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	update(id);
}
void setlazy(int id, Lazy t) {
	tree[id].sum += t.add * tree[id].len % mod;
	tree[id].sum %= mod;
	tree[id].t = tree[id].t + t;
}
void pushdown(int id) {
	if(tree[id].t.add != 0) {
		setlazy(id * 2, tree[id].t);
		setlazy(id * 2 + 1, tree[id].t);
		tree[id].t.add = 0;
	}
}
LL query(int id, int l, int r, int ql, int qr) {
	if(l > r)  return 0;
	if(ql == l && qr == r) return tree[id].sum  % mod;
	int mid = (l + r) / 2;
	pushdown(id);
	if(qr <= mid) return query(id * 2, l, mid, ql, qr);
	else if(ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
	else return (query(id * 2, l, mid, ql, mid) + query(id * 2 + 1, mid + 1, r, mid + 1, qr)) % mod;
}
void modify(int id, int l, int r, int ql, int qr, Lazy t) {
	if(l > r) return;
	if(l == ql && r == qr) {
		setlazy(id, t);
		return;
	}
	int mid = (l + r) / 2;
	pushdown(id);
	if(qr <= mid) modify(id * 2, l, mid, ql,  qr, t);
	else if(ql > mid) modify(id * 2 + 1, mid + 1, r, ql, qr, t);
	else modify(id * 2, l, mid, ql, mid, t), modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
	update(id);
	return;
}
//
int cnt;
void dfs1(int u, int fa) {
	dep[u] = dep[fa] + 1;
	siz[u] = 1;
	F[u] = fa;
	int ma = 0;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].x;
		if(v == fa) continue;
		dfs1(v, u);
		siz[u] += siz[v];
		if(ma < siz[v])
			ma = siz[v], ls[u] = v;
	}
}
void dfs2(int u, int fa) {
	top[u] = fa;
	dfn[u] = ++cnt;
	a[cnt] = val[u];
//	rnk[u] = cnt;
	if(ls[u] == 0) return;
	dfs2(ls[u], fa);
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].x;
		if(ls[u] != v && F[u] != v)
			dfs2(v, v);
	}
}
//
LL get_sum_chain(int u, int v) {
	LL res = 0;
	while(top[u] != top[v]) {
		if(dep[top[u] < dep[top[v]]]) swap(u, v);
		res += query(1, 1, n, dfn[top[u]], dfn[u]);
		res %= mod;
		u = F[top[u]];
	}
	if(dep[u] > dep[v]) swap(u, v);
	return (res + query(1, 1, n, dfn[u], dfn[v])) % mod;
}
LL get_sum_all_sons(int x) {
	return query(1, 1, n, dfn[x], dfn[x] + siz[x] - 1) % mod;
}
//
void updata_chain(int u, int v, int k) {
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) swap(u, v);
		modify(1, 1, n, dfn[top[u]], dfn[u], (Lazy){k});
		u = F[top[u]];
	}
	if(dep[u] > dep[v]) swap(u, v);
	modify(1, 1, n, dfn[u], dfn[v], (Lazy){k});
}
void updata_all_sons(int x, int k) {
	modify(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, (Lazy){k});
}
//
int main () {
	int T, root;
	scanf ("%d %d %d %d", &n, &T, &root, &mod);
	for (int i = 1; i <= n; ++i) scanf ("%d", &val[i]);
	for (int i = 1; i < n; ++i) {
		int u, v;
		scanf ("%d %d", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs1(root, 0);
//	cout << "PPP";
	dfs2(root, 0);
	build(1, 1, n);
//	for (int i = 1; i <= n; ++i)
//		printf("%d ", a[i]);
//	cout << tree[1].sum;
//	cout << "\n\n";
	while(T--) {
		int op, x, y; LL z;
		scanf ("%d", &op);
		if(op == 1) {
			scanf ("%d %d %lld", &x, &y, &z);
			updata_chain(x, y, z);
		} else if(op == 2) {
			scanf ("%d %d", &x, &y);
			printf("%lld\n", get_sum_chain(x, y));
		} else if(op == 3) {
			scanf ("%d %lld", &x, &z);
			updata_all_sons(x, z);
		} else if(op == 4) {
			scanf ("%d", &x);
			printf("%lld\n", get_sum_all_sons(x));
		}
	}
}
//