树剖模板求调 马蜂良好

#include <array>
#include <bits/stdc++.h>
using namespace std;
const int N = 4E5;
int head[N], nxt[N], to[N], cnt, n, m, rt, p, op, x, y, v, a[N], size[N], dep[N], fa[N], son[N], top[N], seg[N], rnk[N];
#define add_edge(u, v) nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v, nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v
void dfs1(int u, int f, int depth) {
    dep[u] = depth, fa[u] = f, size[u] = 1;
    for (int i = head[u]; i; i = nxt[i]) {
        if (to[i] == f) continue;
        dfs1(to[i], u, depth + 1), size[u] += size[to[i]];
        if (size[to[i]] > size[son[u]]) son[u] = to[i];
    }
}
void dfs2(int u, int tp) {
    if (son[u]) seg[son[u]] = ++seg[0], top[son[u]] = top[u], rnk[seg[0]] = son[u], dfs2(son[u], u);
    for (int i = head[u]; i; i = nxt[i])
        if (!top[to[i]]) seg[to[i]] = ++seg[0], rnk[seg[0]] = to[i], top[to[i]] = to[i], dfs2(to[i], u);
}
struct tree {
    int l, r, val, add;
} tr[N];
#define pushup(u) tr[u].val = (tr[u << 1].val + tr[u << 1 | 1].val + p) % p
#define mid (tr[u].l + tr[u].r) >> 1
void change(int u, int val) { tr[u].val = (tr[u].val + (tr[u].r - tr[u].l + 1) * val % p+p) % p, tr[u].add = (tr[u].add + val % p+p) % p; }
void pushdown(int u) {
    if (tr[u].add) change(u << 1, tr[u].add), change(u << 1 | 1, tr[u].add), tr[u].add = 0;
}
void build(int u, int l, int r) {
    if (l == r)
        tr[u] = tree { l, r, a[rnk[l]], 0 };
    else {
        tr[u] = tree { l, r };
        int mmid = (l + r) >> 1;
        build(u << 1, l, mmid), build(u << 1 | 1, mmid + 1, r), pushup(u);
    }
}
void modify(int u, int l, int r, int val) {
    if (tr[u].l >= l && tr[u].r <= r) {
        change(u, val);
    } else {
        pushdown(u);
        if (l <= mid) modify(u << 1, l, r, val);
        if (r > mid) modify(u << 1 | 1, l, r, val);
        pushup(u);
    }
}
int query(int u,int l,int r)
{
    int ans=0;
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        return tr[u].val%p;
    }
    else{
        pushup(u);
        if(l<=mid) ans=(ans+query(u<<1, l, r)%p+p)%p;
        if(r>mid) ans=(ans+query(u<<1|1,l,r)%p+p);
        return ans%p;
    }
}
void tree_add(int x,int y,int val)
{
    while(top[x]!=top[y])
    {
        if(dep[x]<dep[y]) swap(x, y);
        modify(1, seg[top[x]], seg[x], val),x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    modify(1, seg[x], seg[y], val);
}
int tree_query(int x,int y)
{
    int ans=0;
    while(top[x]!=top[y]){
        if(dep[x]<dep[y]) swap(x,y);
        ans=(ans+query(1, seg[top[x]], seg[x])%p+p)%p;
    }
    if(dep[x]>dep[y]) swap(x,y);
    ans=(ans+query(1, seg[x], seg[y])%p+p)%p;
    return ans;
}
int main() {
    cin >> n >> m >> rt >> p;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) cin >> x >> y, add_edge(x, y);
    dfs1(rt, 0, 1);
    dfs2(rt, rt);
    build(1, 1, n);
    while (m--) {
        cin >> op;
        if(op==1) cin>>x>>y>>v,tree_add(x, y, v%p);
        else if(op==2) cin>>x>>y,cout<<tree_query(x, y)<<endl;
        else if(op==3) cin>>x>>y,modify(1, seg[x], seg[x]+size[x]-1,y%p);
        else if(op==4) cin>>x,cout<<query(1, seg[x], seg[x]+size[x]-1)<<endl;
    }
}