抽象代码求调 TLE 8 9 10

#include <ctime>
#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
#define int long long
#define debug puts("qwq")
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
#define all(x) x.begin(), x.end()
namespace FastIO {
    template <typename T = int>
    inline T read() {
        T s = 0, w = 1;
        char c = getchar();
        while (!isdigit(c)) {
            if (c == '-') w = -1;
            c = getchar();
        }
        while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
        return s * w;
    }
    template <typename T>
    inline void read(T &s) {
        s = 0;
        int w = 1;
        char c = getchar();
        while (!isdigit(c)) {
            if (c == '-') w = -1;
            c = getchar();
        }
        while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
        s = s * w;
    }
    template <typename T, typename... Args> inline void read(T &x, Args &...args) {
        read(x), read(args...);
    }
    template <typename T>
    inline void write(T x, char ch) {
        if (x < 0) x = -x, putchar('-');
        static char stk[25];
        int top = 0;
        do {
            stk[top++] = x % 10 + '0', x /= 10;
        } while (x);
        while (top) putchar(stk[--top]);
        putchar(ch);
        return;
    }
    void quit() {
        exit(0);
    }
} using namespace FastIO;
const int N = 1e5 + 11;
vector<int> g[N];
int dep[N], top[N], dfn[N], son[N], siz[N], fa[N], now[N], cnt, mod, a[N];
struct SegmentTree {
    struct Tree {
        int l, r, lzy=0, siz, sum;
    } tree[N];
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mid ((l + r) >> 1)
    void pushup(int k) {
        tree[k].sum = tree[ls].sum + tree[rs].sum + tree[ls].siz * tree[ls].lzy + tree[rs].siz * tree[rs].lzy;
        tree[k].sum %= mod;
    }
    void build(int k, int l, int r) {
        tree[k].l = l;
        tree[k].r = r;
        tree[k].siz = r - l + 1;
        if (l == r) {
            tree[k].sum = a[now[l]];
            return ;
        }
        build(ls, l, mid);
        build(rs, mid + 1, r);
        pushup(k);
    }
    void add(int k, int L, int R, int val) {
        int l = tree[k].l, r = tree[k].r;
        if (L <= l && R >= r) {
            tree[k].lzy += val;
            if (tree[k].lzy >= mod) tree[k].lzy -= mod;
            return ;
        }
        if (L <= mid) add(ls, L, R, val);
        if (R > mid) add(rs, L, R, val);
        pushup(k);
    }
    int query(int k, int L, int R, int sumtag) {
        int l = tree[k].l, r = tree[k].r;
        if (L <= l && R >= r) return tree[k].sum + (tree[k].lzy + sumtag) * tree[k].siz % mod;
        int ans = 0;
        if (L <= mid) ans += query(ls, L, R, sumtag+tree[k].lzy);
        if (R > mid) ans += query(rs, L, R, sumtag+tree[k].lzy);
        ans %= mod;
        return ans;
    }
#undef ls
#undef rs
#undef mid
} seg;
void dfs(int u, int f) {
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    son[u] = 0;
    fa[u] = f;
    for (int i : g[u]) {
        if (i != f) {
            dfs(i, u);
            siz[u] += siz[i];
            if (siz[i] > siz[son[u]]) {
                son[u] = i;
            }
        }
    }
}
void Dfs(int u, int f) {
    dfn[u] = ++cnt;
    now[cnt] = u;
    top[u] = f;
    if (son[u]) Dfs(son[u], f);
    for (int i : g[u]) {
        if (i != fa[u] && i != son[u]) {
            Dfs(i, i);
        }
    }
}
void lca(int u, int v, int z) {
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) swap(u, v);
        seg.add(1, dfn[top[v]], dfn[v], z);
        v = fa[top[v]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    seg.add(1, dfn[u], dfn[v], z);
}
int Get(int u, int v) {
    int ans = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) swap(u, v);
        ans += seg.query(1, dfn[top[v]], dfn[v], 0);
        ans %= mod; 
        v = fa[top[v]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    ans += seg.query(1, dfn[u], dfn[v], 0);
    return ans;
}
signed main() {
    open(s);
    int n, m, s;
    read(n, m, s, mod);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    for (int i = 1; i < n; ++i) {
        int u, v;
        read(u, v);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(s, 0);
    Dfs(s, s);
    seg.build(1, 1, n);
    while (m--) {
        int op, x, y, z;
        read(op);
        if (op == 1) {
            read(x, y, z);
            lca(x, y, z);
        } else if (op == 2) {
            read(x, y);
            write(Get(x, y) % mod, '\n');
        } else if (op == 3) {
            read(x, z);
            seg.add(1, dfn[x], dfn[x] + siz[x] - 1, z);
        } else if (op == 4) {
            read(x);
            write(seg.query(1, dfn[x], dfn[x] + siz[x] - 1, 0) % mod, '\n');
        }
    }
    return 0;
}