本题是非常非常非常纯粹的树剖，利用了重链剖分后下标的性质
不多说上代码就好了
#include <cstdio>
#include <vector>
#define ll long long
using namespace std;
const int N = 1e5 + 5;
int n, m, r;
ll p, a[N], b[N];
vector <int> V[N];
int fa[N], dep[N], siz[N], hson[N], id[N], cnt, top[N];
void dfs1(int sx, int ffa) {
fa[sx] = ffa;
dep[sx] = dep[ffa] + 1;
int maxn = -1;
siz[sx] = 1;
for (auto to : V[sx]) {
if (to == ffa) continue;
dfs1(to, sx);
siz[sx] += siz[to];
if (siz[to] > maxn) {
maxn = siz[to];
hson[sx] = to;
}
}
}
void dfs2(int sx, int topf) {
id[sx] = ++ cnt;
top[sx] = topf;
b[cnt] = a[sx] % p;
if (hson[sx])
dfs2(hson[sx], topf);
for (auto to : V[sx]) {
if (to == fa[sx] || to == hson[sx]) continue;
dfs2(to, to);
}
}
struct sgt {
ll sum[N << 2], lz[N << 2];
void PushUp(int u) {
sum[u] = (sum[u << 1] + sum[u << 1 | 1]) % p;
return ;
}
void build(int u, int l, int r) {
lz[u] = 0;
if (l == r) {
sum[u] = b[l];
return ;
}
int mid = l + r >> 1;
build (u << 1, l, mid);
build (u << 1 | 1, mid + 1, r);
PushUp (u);
return ;
}
void PushDown(int u, int s) {
if (lz[u] == 0) return ;
(lz[u << 1] += lz[u]) %= p;
(lz[u << 1 | 1] += lz[u]) %= p;
(sum[u << 1] += lz[u] * (s - (s >> 1))) %= p;
(sum[u << 1 | 1] += lz[u] * (s >> 1)) %= p;
lz[u] = 0;
return ;
}
void modify(int u, int l, int r, int L, int R, ll k) {
if (L <= l && r <= R) {
(sum[u] += k * (r - l + 1)) %= p;
(lz[u] += k) %= p;
return ;
}
PushDown (u, r - l + 1);
int mid = l + r >> 1;
if (L <= mid)
modify (u << 1, l, mid, L, R, k);
if (mid < R)
modify (u << 1 | 1, mid + 1, r, L, R, k);
PushUp (u);
return ;
}
ll query(int u, int l, int r, int L, int R) {
if (L <= l && r <= R)
return sum[u];
PushDown(u, r - l + 1);
ll ans = 0;
int mid = l + r >> 1;
if (L <= mid)
ans += query(u << 1, l, mid, L, R);
if (mid < R)
ans += query(u << 1 | 1, mid + 1, r, L, R);
return ans % p;
}
void mod_1(int x, int y, ll k) {
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
modify (1, 1, n, id[top[x]], id[x], k);
x = fa[top[x]];
}
else {
modify (1, 1, n, id[top[y]], id[y], k);
y = fa[top[y]];
}
}
if (dep[x] > dep[y])
modify (1, 1, n, id[y], id[x], k);
else modify (1, 1, n, id[x], id[y], k);
return ;
}
ll que_1(int x, int y) {
ll ans = 0;
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
// ans = (ans + query (1, 1, n, id[top[x]], id[x])) % p;
(ans += query (1, 1, n, id[top[x]], id[x])) %= p;
x = fa[top[x]];
}
else {
// ans = (ans + query (1, 1, n, id[top[y]], id[y])) % p;
(ans += query (1, 1, n, id[top[y]], id[y])) %= p;
y = fa[top[y]];
}
}
if (dep[x] > dep[y])
// ans = (ans + query (1, 1, n, id[y], id[x])) % p;
(ans += query (1, 1, n, id[y], id[x])) %= p;
else /*ans = (ans + query (1, 1, n, id[x], id[y])) % p;*/
(ans += query (1, 1, n, id[x], id[y])) %= p;
return ans % p;
}
}tre;
int main() {
// freopen ("tmp.out", "w", stdout);
scanf ("%d%d%d%lld", &n, &m, &r, &p);
for (int i = 1;i <= n; ++ i)
scanf ("%lld", a + i);
for (int i = 1;i < n; ++ i) {
int u, v;
scanf ("%d%d", &u, &v);
V[u].push_back(v);
V[v].push_back(u);
}
dfs1(r, r);
dfs2(r, r);
tre.build(1, 1, n);
while (m --) {
int opt;
scanf ("%d", &opt);
if (opt == 1) {
int x, y;
ll z;
scanf ("%d%d%lld", &x, &y, &z);
tre.mod_1 (x, y, z);
continue;
}
if (opt == 2) {
int x, y;
scanf ("%d%d", &x, &y);
printf ("%lld\n", tre.que_1 (x, y));
continue;
}
if (opt == 3) {
int x;
ll k;
scanf ("%d%lld", &x, &k);
tre.modify(1, 1, n, id[x], id[x] + siz[x] - 1, k);
continue;
}
if (opt == 4) {
int x;
scanf ("%d", &x);
printf ("%lld\n", tre.query(1, 1, n, id[x], id[x] + siz[x] - 1));
continue;
}
}
return 0;
}