树剖 wa on #9 求调

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define L(i,l,r) for(int i=l;i<=r;i++)
#define R(i,r,l) for(int i=r;i>=l;i--)
const int N=1e5+10,M=2e5+10;
int n,m,root,MOD;
int head[N],to[M],nxt[M],v[N],idx;
int timestamp,vt[N],id[N];
int depth[N],hson[N],fa[N],siz[N],top[N];
void add(int u,int v) {
    to[idx]=v;
    nxt[idx]=head[u];
    head[u]=idx++;
}
struct Node {
    int l,r;
    int d,lzy;
};
struct SEG {
#define ls (u<<1)
#define rs (u<<1|1)
    Node tr[N<<2];
    void pushup(int u) {
        tr[u].d=(tr[ls].d+tr[rs].d)%MOD;
    }
    void build(int u,int l,int r) {
        if(l==r) {
            tr[u]= {l,r,vt[l]%MOD,0};
            return;
        }
        tr[u]= {l,r};
        int mid=l+r>>1;
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(u);
    }
    void maketag(int u,int x) {
        int l=tr[u].l,r=tr[u].r;
        int len=r-l+1;
        tr[u].lzy=(tr[u].lzy+x)%MOD;
        tr[u].d=(tr[u].d+len*x%MOD)%MOD;
    }
    void pushdown(int u) {
        if(tr[u].lzy) {
            maketag(ls,tr[u].lzy);
            maketag(rs,tr[u].lzy);
            tr[u].lzy=0;
        }
    }
    int query(int u,int l,int r) {
        if(tr[u].l>=l&&tr[u].r<=r) {
            return tr[u].d;
        }
        pushdown(u);
        int res=0,mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) res=(res+query(ls,l,r))%MOD;
        if(r>mid) res=(res+query(rs,l,r))%MOD;
        return res;
    }
    void update(int u,int l,int r,int x) {
        if(tr[u].l>=l&&tr[u].r<=r) {
            maketag(u,x);
            return;
        }
        pushdown(u);
        int res=0,mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) update(ls,l,r,x);
        if(r>mid) update(rs,l,r,x);
        pushup(u);
    }
} T;
void dfs1(int u,int f,int dep) {
    fa[u]=f;
    depth[u]=dep;
    siz[u]=1; // !
    int mx=-1;
    for(int i=head[u]; ~i; i=nxt[i]) {
        int v=to[i];
        if(v==f) continue; // !
        dfs1(v,u,dep+1);
        siz[u]=(siz[u]+siz[v])%MOD;
        if(siz[v]>mx) {
            mx=siz[v];
            hson[u]=v;
        }
    }
}
void dfs2(int u,int tp) {
    id[u]=++timestamp;
    vt[timestamp]=v[u];
    top[u]=tp;
    if(!hson[u]) return;
    dfs2(hson[u],tp);
    for(int i=head[u]; ~i; i=nxt[i]) {
        int v=to[i];
        if(v==fa[u]||v==hson[u]) continue;
        dfs2(v,v); // ! 轻儿子为重链链头
    }
}
int qSon(int u) {
    return T.query(1,id[u],id[u]+siz[u]-1)%MOD;
}
void updSon(int u,int x) {
    T.update(1,id[u],id[u]+siz[u]-1,x);
}
int qLine(int u,int v) {
    int res=0;
    while(top[u]!=top[v]) {
        if(depth[top[u]]<depth[top[v]]) swap(u,v);
        res=(res+T.query(1,id[top[u]],id[u]))%MOD;
        u=fa[top[u]];
    }
    if(depth[u]>depth[v]) swap(u,v);
    res=(res+T.query(1,id[u],id[v]))%MOD;
    return res;
}
void updLine(int u,int v,int x) {
    x%=MOD;
    while(top[u]!=top[v]) {
        if(depth[top[u]]<depth[top[v]]) swap(u,v);
        T.update(1,id[top[u]],id[u],x); // id[top[u]] 的编号小于 id[u]
        u=fa[top[u]];
    }
    if(depth[u]>depth[v]) swap(u,v);
    T.update(1,id[u],id[v],x);
}
signed main() {
//  freopen("P3384_9.in","r",stdin);
//  freopen("my.out","w",stdout);
    memset(head,-1,sizeof head);
    cin>>n>>m>>root>>MOD;
    L(i,1,n) {
        cin>>v[i];
    }
    L(i,1,n-1) {
        int u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs1(root,0,1);
    dfs2(root,root);
    T.build(1,1,n);
    while(m--) {
        int opt,x,y,z;
        cin>>opt>>x;
        if(opt==1) {
            cin>>y>>z;
            updLine(x,y,z);
        } else if(opt==2) {
            cin>>y;
            cout<<qLine(x,y)<<'\n';
        } else if(opt==3) {
            cin>>z;
            updSon(x,z);
        } else cout<<qSon(x)<<'\n';
    }
    return 0;
}

RT