19分没过样例重链剖分唐氏代码悬关求调

码风依托，请见谅m( )m

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e5;
struct SegmentTree {
    int l, r, val, lz;
};
int n, m, root, mod, val[N + 3];
int hson[N + 3], father[N + 3], size[N + 3], dep[N + 3], seg[N + 3], top[N + 3], rev[N + 3];
SegmentTree tree[(N << 2) + 3];
vector<int> G[N + 3];
void build(int p, int l, int r) {
    tree[p].l = l, tree[p].r = r, tree[p].lz = 0;
    if (l == r) {
        tree[p].val = val[rev[l]];
        return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    tree[p].val = (tree[p << 1].val + tree[p << 1 | 1].val) % mod;
    return;
}
void pushdown(int p) {
    if (tree[p].lz) {
        tree[p << 1].lz += tree[p].lz, tree[p << 1 | 1].lz += tree[p].lz;
        tree[p << 1].val = (tree[p << 1].val + tree[p].lz * (tree[p << 1].r - tree[p << 1].l + 1)) % mod;
        tree[p << 1 | 1].val = (tree[p << 1 | 1].val + tree[p].lz * (tree[p << 1 | 1].r - tree[p << 1 | 1].l + 1)) % mod;
        tree[p].val = (tree[p << 1].val + tree[p << 1 | 1].val) % mod;
    }
}
void update_plus(int p, int l, int r, int k) {
    if (tree[p].r < l || tree[p].l > r) return;
    if (tree[p].l >= l && tree[p].r <= r) {
        tree[p].val = (tree[p].val + k * (tree[p].r - tree[p].l + 1)) % mod;
        tree[p].lz += k;
        return;
    }
    pushdown(p);
    if (tree[p << 1].r >= l) update_plus(p << 1, l, r, k);
    if (tree[p << 1 | 1].l <= r) update_plus(p << 1 | 1, l, r, k);
    tree[p].val = (tree[p << 1].val + tree[p << 1 | 1].val) % mod;
    return;
}
int query(int p, int l, int r) {
    if (tree[p].r < l || tree[p].l > r) return 0;
    if (tree[p].l >= l && tree[p].r <= r) return tree[p].val;
    pushdown(p);
    int ret = 0;
    if (tree[p << 1].r >= l) ret = (ret + query(p << 1, l, r)) % mod;
    if (tree[p << 1 | 1].l <= r) ret = (ret + query(p << 1 | 1, l, r)) % mod;
    return ret;
}
void dfs1(int u, int fa) {
    hson[u] = 0, father[u] = fa, size[u] = 1, dep[u] = dep[fa] + 1;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v != fa) {
            dfs1(v, u);
            size[u] += size[v];
            if (size[v] > size[hson[u]]) hson[u] = v;
        }
    }
    return;
}
void dfs2(int u, int fa) {
    if (hson[u]) {
        seg[hson[u]] = ++seg[0], top[hson[u]] = top[u], rev[seg[0]] = hson[u];
        dfs2(hson[u], u);
    }
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v != fa && !top[v]) {
            seg[v] = ++seg[0];
            top[v] = v;
            rev[seg[0]] = v;
            dfs2(v, u);
        }
    }
    return;
}
void update_path(int x, int y, int z) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        update_plus(1, seg[top[x]], seg[x], z);
        x = father[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    update_plus(1, seg[x], seg[y], z);
    return;
}
int query_path(int x, int y) {
    int ret = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ret = (ret + query(1, seg[top[x]], seg[x])) % mod;
        x = father[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    ret = (ret + query(1, seg[x], seg[y])) % mod;
    return ret;
}
void update_tree(int x, int y) {
    update_plus(1, seg[x], seg[x] + size[x] - 1, y);
    return;
}
int query_tree(int x) {
    return query(1, seg[x], seg[x] + size[x] - 1) % mod;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> root >> mod;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    size[0] = 0, dep[root] = 0, seg[0] = seg[root] = 1, top[root] = root, rev[1] = root;
    dfs1(root, root);
    dfs2(root, root);
    build(1, 1, n);
    while (m--) {
        int op, x, y, z;
        cin >> op;
        switch (op) {
            case 1:
                cin >> x >> y >> z;
                update_path(x, y, z);
                break;
            case 2:
                cin >> x >> y;
                cout << query_path(x, y) << '\n';
                break;
            case 3:
                cin >> x >> y;
                update_tree(x, y);
                break;
            case 4:
                cin >> x;
                cout << query_tree(x) << '\n';
                break;
        }
    }
    return 0;
}