树剖 20 pts WA,只 AC 了 #1 #4 求助

#include <cstdio>
#include <vector>
#define int long long
#define rep(i, j, k) for(int i = j; i <= k; ++i)

const int maxn = (int)1e6 + 5;

int n, q, r, mod, tot, w[maxn], ft[maxn], son[maxn], sum[maxn], dep[maxn], top[maxn], st[maxn], ed[maxn], dfn[maxn << 1];
std::vector<int> G[maxn];

namespace Segment_Tree {

struct _ {
	int val, target, len;
} t[maxn << 2];

inline void swap(int &x, int &y) { x ^= y, y ^= x, x ^= y; }

void build(int p, int l, int r) {
    t[p].len = r - l + 1;
	if(l == r) {
		t[p].val = dfn[l];
		return;
	}
	int lc = p << 1, rc = p << 1 | 1, mid = (l + r) >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	t[p].val = (t[lc].val + t[rc].val) % mod;
	return;
}

inline void pushdown(int p) {
	int l = p << 1, r = p << 1 | 1;
	t[l].val = (t[l].val + t[l].len * t[p].target) % mod;
	t[r].val = (t[r].val + t[r].len * t[p].target) % mod;
	t[l].target = (t[l].target + t[p].target) % mod;
	t[r].target = (t[r].target + t[p].target) % mod;
	t[p].target = 0;
	return;
}

void update(int p, int l, int r, int L, int R, int k) {
    if(L <= l && r <= R) {
        t[p].val = (t[p].val + t[p].len * k % mod) % mod;
        t[p].target = (t[p].target + k) % mod;
        return;
    }
    pushdown(p);
    int lc = p << 1, rc = p << 1 | 1, mid = (l + r) >> 1;
    if(L <= mid)
        update(lc, l, mid, L, R, k);
    if(R > mid)
        update(rc, mid + 1, r, L, R, k);
    t[p].val = (t[lc].val + t[rc].val) % mod;
    return;
}

int query(int p, int l, int r, int L, int R) {
    if(L <= l && r <= R)
        return t[p].val;
    pushdown(p);
    int lc = p << 1, rc = p << 1 | 1, mid = (l + r) >> 1, sum = 0;
    if(L <= mid)
        sum = (sum + query(lc, l, mid, L, R)) % mod;
    if(R > mid)
        sum = (sum + query(rc, mid + 1, r, L, R)) % mod;
    return sum;
}

}
using namespace Segment_Tree;

void dfs1(int u, int fa) {
    ft[u] = fa;
    int len = G[u].size() - 1, mx = 0;
    rep(i, 0, len) {
        int v = G[u][i];
        if(v != fa) {
            dep[v] = dep[u] + 1;
            dfs1(v, u);
            sum[u] += sum[v];
            if(sum[v] > mx) {
                mx = sum[v];
                son[u] = v;
            }
        }
    }
    ++sum[u];
    return;
}

void dfs2(int u, int fa, int tp) {
    top[u] = tp;
    dfn[++tot] = w[u];
    st[u] = tot;
    int len = G[u].size() - 1;
    rep(i, 0, len) {
        int v = G[u][i];
        if(v == son[u])
            dfs2(v, u, tp);
    }
    rep(i, 0, len) {
        int v = G[u][i];
        if(v != fa && v != son[u])
            dfs2(v, u, v);
    }
    dfn[++tot] = w[u];
    ed[u] = tot;
    return;
}

inline void Update(int u, int v, int x) {
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]])
            swap(u, v);
        update(1, 1, tot, st[top[u]], st[u], x);
        update(1, 1, tot, ed[u], ed[top[u]], x);
        u = ft[top[u]];
    }
    if(dep[u] > dep[v])
        swap(u, v);
    update(1, 1, tot, st[u], st[v], x);
    update(1, 1, tot, ed[v], ed[u], x);
    return;
}

inline int Query(int u, int v) {
    int s = 0;
    while(top[u] != top[v]) {
        if(dep[top[u]] < dep[top[v]])
            swap(u, v);
        s = (s + query(1, 1, tot, st[top[u]], st[u])) % mod;
        u = ft[top[u]];
    }
    if(dep[u] > dep[v])
        swap(u, v);
    return s + query(1, 1, tot, st[u], st[v]);
}

signed main() {
    scanf("%lld %lld %lld %lld", &n, &q, &r, &mod);
    rep(i, 1, n)
        scanf("%lld", &w[i]);
    int u, v;
    rep(i, 2, n) {
        scanf("%lld %lld", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs1(r, 0);
    dfs2(r, 0, r);
    build(1, 1, tot);
    int op, x, y, z;
    rep(i, 1, q) {
        scanf("%lld", &op);
        if(op == 1) {
            scanf("%lld %lld %lld", &x, &y, &z);
            Update(x, y, z);
        } else if(op == 2) {
            scanf("%lld %lld", &x, &y);
            printf("%lld\n", Query(x, y) % mod);
        } else if(op == 3) {
            scanf("%lld %lld", &x, &y);
            update(1, 1, tot, st[x], ed[x], y);
        } else {
            scanf("%lld", &x);
            printf("%lld\n", (query(1, 1, tot, st[x], ed[x]) >> 1) % mod);
        }
    }
    return 0;
}