9分代码

#include <bits/stdc++.h>
#define left_son (cur<<1)
#define right_son (left_son|1)
#define mid ((l+r)>>1)

using namespace std;
const int maxn = 1e5 + 5;
int fa[maxn], a[maxn], heavy_son[maxn], w[maxn], dfn[maxn], link_fa[maxn], tr[maxn<<2], siz[maxn], dep[maxn];
bool vis[maxn];
vector<int> neigh[maxn];
vector<int> sons[maxn];
int n, m, rt, p, dfsClock;

int dfs_find_son(int cur) {  // 寻找儿子、重儿子
    vis[cur] = true;
    int size = 1, max_=INT_MIN, max_ind=-1;
    for (int nei : neigh[cur]) {
        if (!vis[nei]) {
            sons[cur].push_back(nei);
            fa[nei] = cur;
            int son_size = dfs_find_son(nei);
            if (son_size > max_)
                max_ = son_size,
                        max_ind = nei;
            size += son_size;
        }
    }
    heavy_son[cur] = max_ind;
    siz[cur] = size;
    return size;
}

void dfs_find_heavy_link(int cur) {
    dfn[cur] = ++dfsClock;
    w[dfn[cur]] = a[cur];
    dep[cur] = dep[fa[cur]]+1;
    if (cur == heavy_son[fa[cur]]) {
        link_fa[cur] = link_fa[fa[cur]];
    } else link_fa[cur] = cur;
    if (heavy_son[cur] != -1)
        dfs_find_heavy_link(heavy_son[cur]);
    for (int son : sons[cur]) {
        if (son != heavy_son[cur])
            dfs_find_heavy_link(son);
    }
}

void push_up(int cur) {
    tr[cur] = (tr[left_son]+tr[right_son])%p;
}

void build(int cur, int l, int r) {
    if (l == r) {tr[cur] = w[l];return;}
    build(left_son, l, mid);
    build(right_son, mid+1, r);
}

void modify(int cur, int l, int r, int x, int y, int k) {
    if (l == r) {
        tr[cur] = (tr[cur]+k)%p;
        return ;
    }
    if (x <= mid) modify(left_son, l, mid, x, y, k);
    if (y > mid) modify(right_son, mid+1, r, x, y, k);
    push_up(cur);
}

int query(int cur, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        return tr[cur];
    }
    int ans = 0;
    if (x <= mid) ans += query(left_son, l, mid, x, y)%p;
    if (y > mid) ans += query(right_son, mid+1, r, x, y)%p;
    return ans%p;
}

void mchain(int x, int y, int k) {
    k %= p;
    while (link_fa[x] != link_fa[y]) {
        if (dep[link_fa[x]] < dep[link_fa[y]]) swap(x, y);
        modify(1, 1, n, dfn[link_fa[x]], dfn[x], k);
        x = fa[link_fa[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    modify(1, 1, n, dfn[x], dfn[y], k);
}

int qchain(int x, int y) {
    int ans = 0;
    while (link_fa[x] != link_fa[y]) {
        if (dep[link_fa[x]] < dep[link_fa[y]]) swap(x, y);
        ans += query(1, 1, n, dfn[link_fa[x]], dfn[x]);
        x = fa[link_fa[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    ans += query(1, 1, n, dfn[x], dfn[y]);
    return ans%p;
}

signed main() {
    scanf("%d%d%d%d", &n, &m, &rt, &p);
    for (int i=1; i<=n; i++)
        scanf("%d", &a[i]);
    for (int i=1; i<n; i++) {
        int f, t;
        scanf("%d%d", &f, &t);
        neigh[f].push_back(t);
        neigh[t].push_back(f);
    }
    dfs_find_son(rt);
    dfs_find_heavy_link(rt);
    build(1, 1, n);
    while (m--) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            int x, y, k;
            scanf("%d%d%d", &x, &y, &k);
            mchain(x, y, k);
        }
        if (op == 2) {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", qchain(x, y));
        }
        if (op == 3) {
            int x, y;
            scanf("%d%d", &x, &y);
            modify(1, 1, n, dfn[x], dfn[x]+siz[x]-1, y);
        }
        if (op == 4) {
            int x;
            scanf("%d", &x);
            printf("%d\n", query(1, 1, n, dfn[x], dfn[x]+siz[x]-1));
        }
    }
    return 0;
}