树链板子求助,赏关

#include <bits/stdc++.h>
using namespace std;
const int N = 1000007;
int n, m, num, cnt, rt, cntt, k, s, mod;
int head[N], size[N], top[N], fa[N], son[N], dep[N], a[N], id[N], w[N];
struct node {
    int v, nxt;
} e[N];
struct tree {
    int sum, lazy;
    int len;
} t[N];

#define lson rt << 1
#define rson rt << 1 | 1

template<class T>inline void read(T &x) {
    x = 0; int f = 0; char ch = getchar();
    while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    x = f ? -x : x;
    return ;
}

void add(int u, int v) {
    e[++num].nxt = head[u], e[num].v = v, head[u] = num;
}

void dfs1(int u, int pre) {
    size[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (v != pre) {
            dep[v] = dep[u] + 1;
            fa[v] = u;
            dfs1(v, u);
            size[u] += size[v];
            if (size[v] > size[son[u]]) son[u] = v;
        }
    }
}

void dfs2(int u, int t) {
    id[u] = ++ cnt;
    a[cnt] = w[u];
    top[u] = t;
    if (son[u]) dfs2(son[u], t);
    for (int i = head[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if (v != fa[u] && v != son[u]) dfs2(v, v);
    }
}

inline void pushup(int rt) {
    t[rt].sum = t[lson].sum + t[rson].sum;
}

void build(int l, int r, int rt) {
    t[rt].len = r - l + 1;
    if (l == r) {
        t[rt].sum = a[l];
        return;
    }
    int m = (l + r) >> 1;
    build(l, m, lson);
    build(m + 1, r, rson);
    pushup(rt);
}

inline void pushdown(int rt) {
    if (t[rt].lazy) {
        t[lson].lazy += t[rt].lazy, t[lson].lazy %= mod;
        t[rson].lazy += t[rt].lazy, t[rson].lazy %= mod;
        t[lson].sum += t[rt].lazy * t[lson].len, t[lson].sum %= mod;
        t[rson].sum += t[rt].lazy * t[rson].len, t[rson].sum %= mod;
        t[rt].lazy = 0;
    }
}

void update(int L, int R, int c, int l, int r, int rt) {
    if (L <= l && r <= R) {
        t[rt].sum += (t[rt].len * c) % mod;
        t[rt].lazy += c;
        return ;
    }
    pushdown(rt);
    int m = (l + r) >> 1;
    if (L <= m) update(L, R, c, l, m, lson);
    if (R > m) update(L, R, c, m + 1, r, rson);
    pushup(rt);
}

int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R) return t[rt].sum;
    pushdown(rt);
    int m = (l + r) >> 1, ans = 0;
    if (L <= m) ans += query(L, R, l, m, lson) % mod;
    if (R > m) ans += query(L, R, m + 1, r, rson) % mod;
    return ans % mod;
}

void update_chain(int x, int y, int z) {
    int fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);
        update(id[fx], id[x], z, 1, cnt, 1);
        x = fa[fx], fx = top[x];
    }
    if (id[x] > id[y]) swap(x, y);
    update(id[x], id[y], z, 1, cnt, 1);
}

int query_chain(int x, int y) {
    int ans = 0, fx = top[x], fy = top[y];
    while (fx != fy) {
        if (dep[fx] < dep[fy]) swap(x, y), swap(fx, fy);
        ans += query(id[fx], id[x], 1, cnt, 1);
        x = fa[fx], fx = top[x];
    }
    if (id[x] > id[y]) swap(x, y);
    ans += query(id[x], id[y], 1, cnt, 1);
    return ans % mod;
}

int main() {
    memset(head, -1, sizeof(head));
    read(n), read(m), read(s), read(mod);
    for (int i = 1; i <= n; ++ i) read(w[i]);
    for (int i = 1, x, y; i < n; ++ i) {
        read(x), read(y);
        add(x, y), add(y, x);
    }
    fa[s] = 1, dep[s] = 0;
    dfs1(s, 0);
    dfs2(s, s);
    build(1, n, 1);
    for (int i = 1, x, y, z; i <= m; ++i) {
        read(k), read(x);
        if (k == 1) {read(y), read(z); update_chain(x, y, z);}
        if (k == 2) {read(y); printf("%d\n", query_chain(x, y));}
        if (k == 3) {read(z); update(id[x], id[x] + size[x] - 1, z, 1, n, 1);}
        if (k == 4) printf("%d\n", query(id[x], id[x] + size[x] - 1, 1, n, 1) % mod);
    }
    return 0;
}