重链剖分与线段树

// Created by qyy on 2024/6/14.

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define PII pair<int, int>
#define endl "\n"

const long long inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int mod;

int n, m;
ll w[N];

int head[N], cnt;
struct Edge{
    int from, to, nxt;
}e[N << 1];
void add(int u, int v){
    e[++cnt].from = u;
    e[cnt].to = v;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

int deep[N], fa[N], siz[N], son[N];
int top[N], dfn[N], tim;
ll nw[N];

void dfs1(int u, int father){
    fa[u] = father;
    deep[u] = deep[father] + 1;
    siz[u] = 1;
    for(int i = head[u]; i != 0; i = e[i].nxt){
        int v = e[i].to;
        if(v == father) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(!son[u] || siz[son[u]] < siz[son[v]]) son[u] = v;
    }
}
void dfs2(int u, int topx){
    dfn[u] = ++tim;
    nw[tim] = w[u];
    top[u] = topx;
    if(!son[u]) return ; // 说明叶子节点了
    dfs2(son[u], topx);
    for(int i = head[u]; i != 0; i = e[i].nxt){
        int v = e[i].to;
        if(v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

int ls(int p){return p << 1;}
int rs(int p){return p << 1|1;}

class SegmentTree{
public:
    ll tree[N << 2|1], tag[N << 2 |1];
    inline void push_up(int p){
        tree[p] = (tree[ls(p)] + tree[rs(p)]) % mod;
    }
    inline void add(int p, int pl, int pr, ll d){
        tree[p] = (tree[p] + (((ll)pr - (ll)pl + 1LL)*d) % mod) % mod;
        tag[p] += d;
        tag[p] %= mod;
    }
    inline void build(int p, int pl, int pr){
        tag[p] = 0;
        if(pl == pr){
            tree[p] = nw[pl];
            return ;
        }
        int mid = (pl + pr) >> 1;
        build(ls(p), pl, mid);
        build(rs(p), mid + 1, pr);
        push_up(p);
    }
    inline void push_down(int p, int pl, int pr){
        if(tag[p]){
            int mid = (pl + pr) >> 1;
            add(ls(p), pl, mid, tag[p]);
            add(rs(p), mid + 1, pr, tag[p]);
            tag[p] = 0;
        }
    }
    inline void update(int L, int R, int p, int pl, int pr, ll d){
        if(L <= pl && pr <= R){
            add(p, pl, pr, d);
            return ;
        }
        push_down(p, pl, pr);
        int mid = (pl + pr) >> 1;
        if(L <= mid){
            update(L, R, ls(p), pl, mid, d);
        }
        if(R >= mid + 1){
            update(L, R, rs(p), mid + 1, pr, d);
        }
        push_up(p);
    }
    inline ll query(int L, int R, int p, int pl, int pr){
        if(L <= pl && pr <= R){
            return tree[p];
        }
        int mid = (pl + pr) >> 1;
        push_down(p, pl, pr);
        ll res = 0;
        if(L <= mid){
            res += query(L, R, ls(p), pl, mid);
            res %= mod;
        }
        if(R >= mid + 1){
            res += query(L, R, rs(p), mid + 1, pr);
            res %= mod;
        }
        return res;
    }
};
SegmentTree seg;

ll query_path(int x, int y){
    ll res = 0;
    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        res += seg.query(dfn[top[x]], dfn[x], 1, 1, n);
        res %= mod;
        x = fa[top[x]];
    }
    if(deep[x] < deep[y]) swap(x, y);
    res += seg.query(dfn[y], dfn[x], 1, 1, n);
    return res % mod;
}

void update_path(int x, int y, ll dx){
    while(top[x] != top[y]){
        if(deep[top[x]] < deep[top[y]]) swap(x, y);
        seg.update(dfn[top[x]], dfn[x], 1, 1, n, dx);
        x = fa[top[x]];
    }
    if(deep[x] < deep[y]) swap(x, y);
    seg.update(dfn[y], dfn[x], 1, 1, n, dx);
}

// 恐怕需要另外的数组，记录这个节点的开始 dfn 到结束 dfn
ll query_tree(int u){
    int l = dfn[u], r = dfn[u] + siz[u] - 1;
    return seg.query(l, r, 1, 1, n);
}

void update_tree(int u, ll x){
    int l = dfn[u], r = dfn[u] + siz[u] - 1;
    seg.update(l, r, 1, 1, n, x);
}

void solve() {
    int root;
    cin >> n >> m >> root >> mod;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
        w[i] %= mod;
    }
    for(int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    dfs1(root, 0);
    dfs2(root, root);

    seg.build(1, 1, n);
    for(int i = 1; i <= m; i++){
        int op, x, y, z;
        cin >> op;
        if(op == 1){
            cin >> x >> y >> z;
            update_path(x, y, z);
        }else if(op == 2){
            cin >> x >> y;
            cout << query_path(x, y) << endl;
            // ask;
        }else if(op == 3){
            cin >> x >> z;
            update_tree(x, z);
        }else{
            // ask;
            cin >> x;
            cout << query_tree(x) << endl;
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}