树剖求助 码风还算河里

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
template <class T>
inline void read(T &res){
    char c;bool f=0;
    while(!isdigit(c=getchar())) if(c=='-') f=1;
    res=(c^48);
    while(isdigit(c=getchar())) res=(res<<1)+(res<<3)+(c^48);
    if(f) res=~res+1;
}
int n,m,r,op,x,y,z,f[N],cnt;
long long p,a[N];
struct Edge{
    int v,nxt;
}e[N*2];
void insert(int u,int v){
    e[++cnt]=(Edge){v,f[u]};
    f[u]=cnt;
}
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)

struct Segtree{
    struct Tree{
        long long sum;
        long long tag_add;
    }t[N*4];
    void build(int u,int l,int r){
        if(l==r) {t[u].sum=a[l]%p; return ;}
        build(ls,l,mid);
        build(rs,mid+1,r);
        t[u].sum=(t[ls].sum+t[rs].sum)%p;
    }
    void up(int u,int l,int r,int x) {t[u].tag_add+=x; (t[u].sum+=(r-l+1)*x)%=p;}
    void push_down(int u,int l,int r){
        if(t[u].tag_add){
            up(ls,l,mid,t[u].tag_add);
            up(rs,mid+1,r,t[u].tag_add);
            t[u].tag_add=0;
        }
    }
    long long query(int u,int l,int r,int ql,int qr){
        if(qr<l||r<ql) return 0;    
        if(ql<=l&&qr>=r) return t[u].sum%p;
        push_down(u,l,r);
        return (query(ls,l,mid,ql,qr)+query(rs,mid+1,r,ql,qr))%p;
    }
    void modify(int u,int l,int r,int ql,int qr,int x){
        if(qr<l||r<ql) return ;
        if(ql<=l&&r<=qr) return up(u,l,r,x);
        push_down(u,l,r);
        modify(ls,l,mid,ql,qr,x);
        modify(rs,mid+1,r,ql,qr,x);
        t[u].sum=(t[ls].sum+t[rs].sum)%p;
    }
}seg;
int fa[N],son[N],top[N],ind;
long long dep[N],siz[N],ver[N],dfn[N];
void dfs(int u){
    siz[u]=1;dep[u]=dep[fa[u]]+1;
    for(int i=f[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v!=fa[u]){
            fa[v]=u;
            dfs(v);
            siz[u]+=siz[v];
            if(siz[v]>siz[son[u]]) son[u]=v;
        }
    }
}
void dfs2(int u,int t){
    top[u]=t;
    ver[++ind]=u,dfn[u]=ind;
    if(son[u]) dfs2(son[u],t);
    for(int i=f[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
    }
}
int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
void add(int u,int v,int x){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        seg.modify(1,1,n,dfn[top[u]],dfn[u],x%p);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    seg.modify(1,1,n,dfn[u],dfn[v],x%p);
}
long long sum(int u,int v){
    long long res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        (res+=seg.query(1,1,n,dfn[top[u]],dfn[u]))%=p;
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    return (res+seg.query(1,1,n,dfn[u],dfn[v]))%p;
}
int main(){
    read(n);read(m);read(r);read(p);
    for(int i=1;i<=n;i++) read(a[i]);
    seg.build(1,1,n);
    for(int i=1;i<n;i++){
        int u,v;
        read(u);read(v);
        insert(u,v);
        insert(v,u);
    }
    dfs(r);dfs2(r,r);
    for(int i=1;i<=m;i++){
        read(op);
        if(op==1){
            read(x);read(y);read(z);
            add(x,y,z);
        }
        else if(op==2){
            read(x);read(y);
            printf("%lld\n",sum(x,y)%p);
        }
        else if(op==3){
            read(x);read(z);
            seg.modify(1,1,n,dfn[x],dfn[x]+siz[x]-1,z);
        }
        else{
            read(x);
            printf("%lld\n",seg.query(1,1,n,dfn[x],dfn[x]+siz[x]-1)%p);
        }
    }
    return 0;
}