萌新刚学 OI 一毫秒，树剖板子求调

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define self tr[p]
#define rson tr[tr[p].rs]
#define lson tr[tr[p].ls]
int n, q, root, P;
int a[100005], an[100005];
struct Node {
    ll vl, mk;
    int ls, rs;
} tr[200005];
int cnt;
int NewNode() {
    int p = ++cnt;
    self.ls = self.rs = self.mk = self.vl = 0;
    return p;
}
int Build(int l, int r) {
    int p = NewNode(), mid = l + r >> 1;
    if (l == r) {
        self.vl = an[l];
        return p;
    }
    self.ls = Build(l, mid);
    self.rs = Build(mid + 1, r);
    self.vl = (lson.vl + 1ll * rson.vl) % P;
    return p;
}
void Pushdown(int p, int l, int r) {
    int mid = l + r >> 1;
    if (!self.mk) return;
    if (!self.ls) {
        self.ls = NewNode();
    }
    if (!self.rs) {
        self.rs = NewNode();
    }
    lson.vl = (lson.vl + 1ll * (mid - l + 1) * self.mk % P) % P;
    rson.vl = (rson.vl + 1ll * (r - mid) * self.mk % P) % P;
    lson.mk = rson.mk = self.mk;
    self.mk = 0;
    self.vl = (lson.vl + 1ll * rson.vl) % P;
}
int Query(int l, int r, int cl, int cr, int p) {
    if (cl > r || cr < l) return 0;
    if (!p) return 0;
    if (cl >= l && cr <= r) {
        return self.vl;
    }
    Pushdown(p, cl, cr);
    int mid = cl + cr >> 1;
    return (Query(l, r, cl, mid, self.ls) + 1ll * Query(l, r, mid + 1, cr, self.rs)) % P;
}
void Modify(int l, int r, int cl, int cr, int &p, int w) {
    if (cl > r || cr < l) return;
    if (!p) p = NewNode();
    if (cl >= l && cr <= r) {
        self.vl = (self.vl + 1ll * (cr - cl + 1) * w % P) % P;
        self.mk = w;
        return;
    }
    Pushdown(p, cl, cr);
    int mid = cl + cr >> 1;
    Modify(l, r, cl, mid, self.ls, w);
    Modify(l, r, mid + 1, cr, self.rs, w);
    self.vl = (lson.vl + 1ll * rson.vl) % P;
}
struct Edge {
    int to, next;
} e[200005];
int troot;
int head[100005], len;
void Insert(int u, int v) {
    e[++len].to = v;
    e[len].next = head[u];
    head[u] = len;
}
int prt[100005], dep[100005], siz[100005], hson[100005], id[100005], htop[100005], tcn;
void dfs1(int u, int fa, int d) {
    prt[u] = fa;
    dep[u] = d;
    siz[u] = 1;
    int mx = -1;
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v != fa) {
            dfs1(v, u, d + 1);
            siz[u] += siz[v];
            if (siz[v] > mx) {
                mx = siz[v];
                hson[u] = v;
            }
        }
    }
}
void dfs2(int u, int top) {
    htop[u] = top;
    id[u] = ++tcn;
    an[tcn] = a[u];
    if (!hson[u]) return;
    dfs2(hson[u], top);
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].to;
        if (v != prt[u] && v != hson[u]) {
            dfs2(v, v);
        }
    }
}
int QuerySub(int u) {
    return Query(id[u], id[u] + siz[u] - 1, 1, n, troot);
}
void ModifySub(int u, int w) {
    w %= P;
    Modify(id[u], id[u] + siz[u] - 1, 1, n, troot, w);
}
int QueryChain(int u, int v) {
    int res = 0;
    while (htop[u] != htop[v]) {
        if (dep[htop[u]] < dep[htop[v]]) swap(u, v);
        res = (res + 1ll * Query(id[htop[u]], id[u], 1, n, troot)) % P;
        // cout << htop[u] << " " << u << endl;
        u = prt[htop[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    res = (res + 1ll * Query(id[u], id[v], 1, n, troot)) % P;
    // cout << u << " " << v << endl;
    return res;
}
void ModifyChain(int u, int v, int w) {
    w %= P;
    while (htop[u] != htop[v]) {
        if (dep[htop[u]] < dep[htop[v]]) swap(u, v);
        Modify(id[htop[u]], id[u], 1, n, troot, w);
        u = prt[htop[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    Modify(id[u], id[v], 1, n, troot, w);
}
int main() {
    scanf("%d%d%d%d", &n, &q, &root, &P);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        Insert(u, v);
        Insert(v, u);
    }
    dfs1(root, 0, 1);
    dfs2(root, root);
    troot = Build(1, n);
    while (q--) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            ModifyChain(u, v, w);
        }
        else if (op == 2) {
            int u, v;
            scanf("%d%d", &u, &v);
            printf("%d\n", QueryChain(u, v));
        }
        else if (op == 3) {
            int u, w;
            scanf("%d%d", &u, &w);
            ModifySub(u, w);
        }
        else {
            int u;
            scanf("%d", &u);
            printf("%d\n", QuerySub(u));
        }
    }
    return 0;
}