被推荐做此《线段树好题》而wa 30pts

rt,线段树能过

#include <bits/stdc++.h>
#define int long long
#define inf 2147483647
using namespace std;
const int maxn = 1e5 + 5;
int n, m, R, mod, w[maxn];
int dep[maxn], son[maxn], fa[maxn], siz[maxn];
vector<int> g[maxn];
inline void dfs1(int p, int f) {
    int mxson = -1;
    siz[p] = 1;
    for (int i = 0; i < g[p].size(); ++i) {
        int v = g[p][i];
        if (v == f) continue;
        fa[v] = p; dep[v] = dep[p] + 1;
        dfs1(v, p);
        siz[p] += siz[v];
        if (siz[v] > mxson) {
            son[p] = v, mxson = siz[v];
        }
    }
}
int top[maxn], id[maxn], nw[maxn], dfn;
inline void dfs2(int p, int tp) {
    top[p] = tp;
    id[p] = ++dfn;
    nw[id[p]] = w[p];
//  cerr << nw[id[p]] << endl;
    if (!son[p]) return ;
    dfs2(son[p], tp);
    for (int i = 0; i < g[p].size(); ++i) {
        int v = g[p][i];
        if (v != son[p] && v != fa[p]) {
            dfs2(v, v);
        }
    }
}
struct treenode {
    int l, r, val, tag;
} segtree[4 * maxn];
int lch(int p) {
    return (p << 1);
}
int rch(int p) {
    return (p << 1) + 1;
}
void push_up(int p) {
    segtree[p].val = (segtree[lch(p)].val + segtree[rch(p)].val) % mod;
}
inline void build(int l, int r, int p) {
    segtree[p].l = l, segtree[p].r = r;
    if (l == r) {
        segtree[p].val = nw[l] % mod;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, lch(p));
    build(mid + 1, r, rch(p));
    push_up(p);
}
void update_tag(int p, int delta) {
    int l = segtree[p].l, r = segtree[p].r;
    segtree[p].tag += delta;
    segtree[p].tag %= mod;
    segtree[p].val += ((r - l + 1) % mod * (delta % mod)) % mod;
}
void push_down(int p) {
    update_tag(lch(p), segtree[p].tag);
    update_tag(rch(p), segtree[p].tag);
    segtree[p].tag = 0;
}
inline void update(int ul, int ur, int delta, int p) {
    int l = segtree[p].l, r = segtree[p].r;
    if (ul > r || ur < l) return;
    if (ul <= l && r <= ur) {
        update_tag(p, delta);
        return ;
    }
    push_down(p);
    int mid = (l + r) >> 1;
    if (ul <= mid) update(ul, ur, delta, lch(p));
    if (ur > mid) update(ul, ur, delta, rch(p));
    push_up(p);
}
inline int query(int ql, int qr, int p) {
    int l = segtree[p].l, r = segtree[p].r;
    if (ql <= l && r <= qr) {
        return segtree[p].val % mod;
    }
    push_down(p);
    int mid = (l + r) >> 1, res = 0;
    if (ql <= mid) res += query(ql, qr, lch(p)), res %= mod;
    if (qr > mid) res += query(ql, qr, rch(p)), res %= mod;
    push_up(p);
    return res;
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if (ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
    return;
}
signed main() {
    cin >> n >> m >> R >> mod;
    for (int i = 1; i <= n; ++i) w[i] = read();
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dep[R] = 1;
    dfs1(R, -1);
    dfs2(R, R);
    build(1, n, 1);
    for (int i = 1; i <= m; ++i) {
        int tp = read();
        if (tp == 1) {
            int x = read(), y = read(), z = read();
            while (top[x] != top[y]) {
                if (dep[x] < dep[y]) swap(x, y);
                update(id[top[x]], id[x], z, 1);
                x = fa[top[x]];
            }
            if (dep[x] < dep[y]) swap(x, y);
            update(id[y], id[x], z, 1);
        } else if (tp == 2) {
            int x = read(), y = read();
            int res = 0;
//          cerr << x << ' ' << y << endl;
            while (top[x] != top[y]) {
                if (dep[x] < dep[y]) swap(x, y);
//              cerr << top[x] << ' ' << id[x] << endl;
                res += query(id[top[x]], id[x], 1);
                res %= mod;
                x = fa[top[x]];
//              cerr << res << ' ' << x << endl;
            }
            if (dep[x] < dep[y]) swap(x, y);
            res += query(id[y], id[x], 1);
            res %= mod;
            write(res);
            puts("");
        } else if (tp == 3) {
            int x = read(), z = read();
            update(id[x], id[x] + siz[x] - 1, z, 1);
        } else {
            int x = read();
            write(query(id[x], id[x] + siz[x] - 1, 1) % mod);
            puts("");
        }
    }
    return 0;
}
/*
8 10 2 448348
458 718 447 857 633 264 238 944 
1 2
2 3
3 4
6 2
1 5
5 7
8 6
3 7 611
4 6
3 1 267
3 2 111
1 6 3 153
3 7 673
4 8
2 6 1
4 7
3 4 228
*/