28pts AC#1#3#11求条玄关

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5;
int head[maxn << 2], to[maxn << 2], nxt[maxn << 2], cnt, siz[maxn << 2], fa[maxn << 2], dep[maxn << 2], son[maxn << 2],e, top[maxn << 2], seg[maxn << 2], num[maxn << 2], n, m, r, p, w[maxn << 2], res;
void insert(int u, int v) { nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v;}
struct tree {
    int l, r, len, val, laz;
} tr[maxn << 2];
void dfs1(int u, int f, int depth, int maxson = -1) {
    dep[u] = depth, siz[u] = 1, fa[u] = f;
    for (int i = head[u]; i; i = nxt[i]) {
        if (to[i] == f) continue;
        dfs1(to[i], u, depth + 1), siz[u] += siz[to[i]];
        if (siz[to[i]] > maxson) son[u] = to[i], maxson = siz[to[i]];
    }
}
void dfs2(int u, int tp) {
    top[u] = tp, seg[u] = ++e, num[e] = u;
    if (!son[u]) return;
    dfs2(son[u], tp);
    for (int i = head[u]; i; i = nxt[i]) {
        if (to[i] == son[u] || to[i] == fa[u]) continue;
        dfs2(to[i], to[i]);
    }
}
void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = tree { l, r, l - r + 1, w[num[l]] % p, 0 };
    } else {
        tr[u] = tree { l, r, l - r + 1 ,0,0};
        build(u << 1, l, (l + r) >>1);
        build(u << 1 | 1, (l + r)/2+1, r);
        tr[u].val = (tr[u << 1].val + tr[u << 1 | 1].val) % p;
    }
}
void pushdown(int u) {
    tr[u << 1].val = (tr[u << 1].val + tr[u << 1].len * tr[u].laz) % p;
    tr[u << 1 | 1].val = (tr[u << 1 | 1].val + tr[u << 1 | 1].len * tr[u].laz) % p;
    tr[u << 1].laz += tr[u].laz;
    tr[u << 1 | 1].laz += tr[u].laz;
    tr[u].laz = 0;
}
void modify(int u, int l, int r, int val) {
    if (l <= tr[u].l && tr[u].r <= r)
        tr[u].val += val * tr[u].len, tr[u].laz += val;
    else {
        if (tr[u].laz) pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if (l <= mid) modify(u << 1, l, r, val);
        if (r > mid) modify(u << 1 | 1, l, r, val);
        tr[u].val = (tr[u << 1].val + tr[u << 1 | 1].val) % p;
    }
}
void query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) {
        res += tr[u].val, res %= p;
    } else {
        if (tr[u].laz) pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if (l <= mid) query(u << 1, l, r);
        if (r > mid) query(u << 1 | 1, l, r);
    }
}
void treeadd(int x, int y, int val) {
    val%=p;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        modify(1, seg[top[x]], seg[x], val), x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    modify(1, seg[x], seg[y], val);
}
int treesum(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res = 0;
        query(1, seg[top[x]], seg[x]), x = fa[top[x]];
        ans += res;
        ans %= p;
    }
    if (dep[x] > dep[y]) swap(x, y);
    res = 0, query(1, seg[x], seg[y]), ans += res;
    return ans % p;
}
int op, x, y, z,a,b;
signed main() {
    scanf("%lld %lld %lld %lld", &n, &m, &r, &p);
    for (int i = 1; i <= n; i++) scanf("%lld ", &w[i]);
    for (int i = 1; i < n; i++) scanf("%lld %lld", &a, &b), insert(a, b),insert(b,a);
    dfs1(r, 0, 1);
    dfs2(r, r);
    build(1, 1, n);
    for (int i = 1; i <= m; i++) {
        scanf("%lld", &op);
        if (op == 1)
            scanf("%lld %lld %lld", &x, &y, &z), res=0,treeadd(x, y, z % p);
        else if (op == 2)
            scanf("%lld %lld", &x, &y), res = 0, printf("%lld\n", treesum(x, y) % p);
        else if (op == 3)
            scanf("%lld %lld", &x, &y), res=0,modify(1, seg[x], seg[x] + siz[x] - 1, y);
        else if (op == 4)
            scanf("%lld", &x), res = 0, query(1, seg[x], seg[x] + siz[x] - 1), printf("%lld\n", res%p);
    }
    return 0;
}

/kel 思路上借鉴题解想按照自己的习惯改成线段树数组 结果就rt