树链剖分

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
const int N = 100005;
vector<int> adj[N];
int low[N], son[N], fa[N], deep[N];
int top[N], dfn[N], revdfn[N], tot;
void dfs1(int u, int p) {
    deep[u] = deep[p] + 1;
    fa[u] = p;
    low[u] = -1;
    son[u] = 1;
    for (auto &to : adj[u]) {
        if (to == p) continue;
        dfs1(to, u);
        son[u] += son[to];
        if (low[u] == -1 || son[to] > son[low[u]]) {
            low[u] = to;
        }
    }
}
void dfs2(int u, int p) {
    top[u] = p;
    dfn[u] = ++tot;
    revdfn[tot] = u;
    if (low[u] == -1) {
        return;
    }
    dfs2(low[u], p);
    for (auto &to : adj[u]) {
        if (to == low[u] || to == fa[u]) {
            continue;
        }
        dfs2(to, to);
    }
}
int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) {
            swap(x, y);
        }
        x = fa[top[x]];
    }
    if (deep[x] > deep[y]) {
        swap(x, y);
    }
    return x;
}
int a[N];
int P;
struct Node {
    int L, R;
    i64 sum;
} tr[N << 2];
i64 lazy[N << 2];
void pushup(int p) {
    tr[p].sum = (tr[p << 1].sum + tr[p << 1 | 1].sum) % P;
}
void pushtag(int p, i64 k) {
    tr[p].sum = (tr[p].sum + (tr[p].R - tr[p].L + 1) * k % P) % P;
    lazy[p] = (lazy[p] + k) % P;
}
void pushdown(int p) {
    if (lazy[p] != 0) {
        pushtag(p << 1, lazy[p]);
        pushtag(p << 1 | 1, lazy[p]);
        lazy[p] = 0;
    }
}
void build(int p, int L, int R) {
    tr[p].L = L;
    tr[p].R = R;
    if (L == R) {
        tr[p].sum = a[revdfn[L]];
        return;
    }
    int mid = L + R >> 1;
    build(p << 1, L, mid);
    build(p << 1 | 1, mid + 1, R);
    pushup(p);
}
void modify(int p, int QL, int QR, i64 k) {
    if (QL <= tr[p].L && tr[p].R <= QR) {
        pushtag(p, k);
        return;
    }
    pushdown(p);
    int mid = tr[p].L + tr[p].R >> 1;
    if (QL <= mid) {
        modify(p << 1, QL, QR, k);
    }
    if (QR >= mid + 1) {
        modify(p << 1 | 1, QL, QR, k);
    }
    pushup(p);
}
i64 query(int p, int QL, int QR) {
    if (QL <= tr[p].L && tr[p].R <= QR) {
        return tr[p].sum;
    }
    pushdown(p);
    int mid = tr[p].L + tr[p].R >> 1;
    i64 res = 0;
    if (QL <= mid) {
        res = (res + query(p << 1, QL, QR)) % P;
    }
    if (QR >= mid + 1) {
        res = (res + query(p << 1 | 1, QL, QR)) % P;
    }
    return res;
}
void addPath(int x, int y, int k) {
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) {
            swap(x, y);
        }
        modify(1, dfn[top[x]], dfn[x], k);
        x = fa[top[x]];
    }
    if (deep[x] > deep[y]) {
        swap(x, y);
    }
    modify(1, dfn[x], dfn[y], k);
}
i64 queryPath(int x, int y) {
    i64 res = 0;
    while (top[x] != top[y]) {
        if (deep[top[x]] < deep[top[y]]) {
            swap(x, y);
        }
        res = (res + query(1, dfn[top[x]], dfn[x])) % P;
        x = fa[top[x]];
    }
    if (deep[x] > deep[y]) {
        swap(x, y);
    }
    res = (res + query(1, dfn[x], dfn[y])) % P;
    return res;
}
void addSon(int x, int k) {
    modify(1, dfn[x], dfn[x] + son[x] - 1, k);
}
i64 querySon(int x) {
    return query(1, dfn[x], dfn[x] + son[x] - 1);
}
int main() {
    int n, m, rt;
    cin >> n >> m >> rt >> P;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    for (int i = 1 ; i < n ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs1(rt, 0);
    dfs2(rt, rt);
    build(1, 1, n);
    for (int i = 1 ; i <= m ; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y, z;
            cin >> x >> y >> z;
            addPath(x, y, z);
        } else if (op == 2) {
            int x, y;
            cin >> x >> y;
            cout << queryPath(x, y) % P << "\n";
        } else if (op == 3) {
            int x, z;
            cin >> x >> z;
            addSon(x, z);
        } else {
            int x;
            cin >> x;
            cout << querySon(x) % P << "\n";
        }
    }
    return 0;
}