萌新刚学树剖，MLE on #1~#10

rt ，看题解发现开到2e5都没爆，为啥我这个就爆了。。

本地测试#1数据点通过，洛谷评测MLE。但是洛谷能ac最后一个点。。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;

class SegmentTree {
private:
    int tr[4 * N], lazy[4 * N];
    int _n, _P, _a[N];

    int lson(int id) {
        return id * 2;
    }

    int rson(int id) {
        return id * 2 + 1;
    }

    int pushup(int id) {
        tr[id] = tr[lson(id)] + tr[rson(id)];
        tr[id] %= _P;
    }

    void pushdown(int id, int l, int r) {
        if (!lazy[id]) return;
        lazy[lson(id)] += lazy[id];
        lazy[lson(id)] %= _P;
        lazy[rson(id)] += lazy[id];
        lazy[rson(id)] %= _P;
        int mid = (l + r) >> 1;
        tr[lson(id)] += (mid - l + 1) * lazy[id] % _P;
        tr[lson(id)] %= _P;
        tr[rson(id)] += (r - mid) * lazy[id] % _P;
        tr[rson(id)] %= _P;
        lazy[id] = 0;
    }

    void _update(int id, int l, int r, int x, int y, int v) {
        v %= _P;
        if (x <= l && r <= y) {
            tr[id] += (r - l + 1) * v % _P;
            tr[id] %= _P;
            lazy[id] += v % _P;
            lazy[id] %= _P;
            return;
        }
        pushdown(id, l, r);
        int mid = (l + r) >> 1;
        if (x <= mid) {
            _update(lson(id), l, mid, x, y, v);
        }
        if (y > mid) {
            _update(rson(id), mid + 1, r, x, y, v);
        }
        pushup(id);
    }

    int _query(int id, int l, int r, int x, int y) {
        if (x <= l && r <= y) {
            return tr[id];
        }
        pushdown(id, l, r);
        int mid = (l + r) >> 1;
        int ans = 0;
        if (x <= mid) {
            ans += _query(lson(id), l, mid, x, y);
            ans %= _P;
        }
        if (y > mid) {
            ans += _query(rson(id), mid + 1, r, x, y);
            ans %= _P;
        }
        return ans % _P;
    }

    void _build(int id, int l, int r) {
        if (l == r) {
            tr[id] = _a[l];
            return;
        }
        int mid = (l + r) >> 1;
        _build(lson(id), l, mid);
        _build(rson(id), mid + 1, r);
        pushup(id);
    }

public:
    void update(int x, int y, int v) {
        _update(1, 1, _n, x, y, v);
    }

    int query(int x, int y) {
        return _query(1, 1, _n, x, y);
    }

    void build(int a[], int n, int P) {
        memset(lazy, 0, sizeof(lazy));
        _P = P;
        _n = n;
        for (int i = 1; i <= n; i++) _a[i] = a[i];
        _build(1, 1, _n);
    }
};

vector<int> G[N];

void addEdge(int u, int v) {
    G[u].push_back(v);
}

int n, m, r, p;
int a[N], w[N];
int dep[N], siz[N], hson[N], fa[N];
int top[N], dfn[N], cnt = 0;
SegmentTree tr;

void dfs1(int u) {
    siz[u] = 1;
    hson[u] = -1;
    for (auto v : G[u]) {
        if (dep[v]) continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs1(v);
        if (hson[u] == -1 || siz[v] > siz[hson[u]]) {
            hson[u] = v;
        }
        siz[u] += siz[v];
    }
}

void dfs2(int u, int root) {
    top[u] = root;
    dfn[u] = ++cnt;
    w[dfn[u]] = a[u];
    if (hson[u] == -1) return;
    dfs2(hson[u], root);
    for (auto v : G[u]) {
        if (v == hson[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

int rangeQuery(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += tr.query(dfn[top[x]], dfn[x]) % p;
        ans %= p;
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    ans += tr.query(dfn[y], dfn[x]) % p;
    ans %= p;
    return ans;
}

void rangeUpdate(int x, int y, int v) {
    v %= p;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        tr.update(dfn[top[x]], dfn[x], v % p);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    tr.update(dfn[y], dfn[x], v % p);
}

int subtreeQuery(int x) {
    return tr.query(dfn[x], dfn[x] + siz[x] - 1) % p;
}

void subtreeUpdate(int x, int v) {
    v %= p;
    tr.update(dfn[x], dfn[x] + siz[x] - 1, v);
}

int main() {
    scanf("%d%d%d%d", &n, &m, &r, &p);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n - 1; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        addEdge(x, y);
        addEdge(y, x);
    }
    dep[r] = 1;
    dfs1(r);
    dfs2(r, r);
    tr.build(w, n, p);
    while (m--) {
        int op, x, y, z;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d%d%d", &x, &y, &z);
            rangeUpdate(x, y, z);
        } else if (op == 2) {
            scanf("%d%d", &x, &y);
            printf("%d\n", rangeQuery(x, y));
        } else if (op == 3) {
            scanf("%d%d", &x, &z);
            subtreeUpdate(x, z);
        } else {
            scanf("%d", &x);
            printf("%d\n", subtreeQuery(x));
        }
    }
    return 0;
}