萌新刚学OI两天，树剖求条

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
int n,m,r,a[N],mod;
int deep[N],dfn[N],son[N],siz[N],top[N],fa[N];
int to[N<<1],nxt[N<<1],head[N],cnt;
int newa[N],tr[N<<2],tag[N<<2];
void addtag(int p,int pl,int pr,int d){
    tag[p]+=d;
    tr[p]+=d*(pr-pl+1);tr[p]%=mod;
}
void pushdown(int p,int pl,int pr){
    if(tag[p]){
        int d=tag[p];
        tag[p<<1]+=d,tag[p<<1|1]+=d;
        int mid=(pl+pr)>>1;
        tr[p<<1]+=d*(mid-pl+1),tr[p<<1|1]+=d*(pr-mid);
        tr[p<<1]%=mod,tr[p<<1|1]%=mod;
        tag[p]=0;
    }
}
void build(int i,int l,int r){
    if(l==r){
        tag[i]=newa[l];
        return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);build(i<<1|1,mid+1,r);
    tr[i]=tr[i<<1]+tr[i<<1|1];tr[i]%=mod;
}
void update(int i,int l,int r,int pl,int pr,int d){
    if(pl>=l and pr<=r ){
        addtag(i,pl,pr,d);
        return;
    }
    pushdown(i,pl,pr);
    int mid=(pl+pr)>>1;
    if(mid>=l) update(i<<1,l,r,pl,mid,d);
    if(mid<r) update(i<<1|1,l,r,mid+1,r,d);
    tr[i]=tr[i<<1]+tr[i<<1|1];tr[i]%=mod;
}
int query(int i,int l,int r,int pl,int pr){
    if(pl>=l and pr<=r) return tr[i];
    pushdown(i,pl,pr);
    int mid=(pl+pr)>>1;int res=0;
    if(mid>=l) res=query(i<<1,l,r,pl,mid);
    if(mid<r) res+=query(i<<1|1,l,r,mid+1,pr);
    res%=mod;
    return res;
}
void add(int u,int v){
    to[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt;
}
int tot;
void dfs1(int x,int f){
    fa[x]=f,siz[x]=1,deep[x]=deep[f]+1;
    int num=0;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y!=f) dfs1(y,x);
        siz[x]+=siz[y];
        if(siz[y]>num){
            num=siz[y];
            son[x]=y;
        }
    }
}
void dfs2(int x,int topx){
    dfn[x]=++tot, newa[tot]=a[x];
    top[x]=topx;
    if(!son[x]) return;
    dfs2(son[x],topx);
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y!=fa[x] and y!=son[x]) dfs2(y,y);
    }
}
void updline(int x,int y,int d){
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        update(1,dfn[top[x]],dfn[x],1,n,d);
        x=fa[top[x]];
    }
    if(deep[x]>deep[y]) swap(x,y);
    update(1,dfn[x],dfn[y],1,n,d);
}
int qryline(int x,int y){
    int res=0;
    while(top[x]!=top[y]){
        if(deep[top[x]]<deep[top[y]]) swap(x,y);
        res+=query(1,dfn[top[x]],dfn[x],1,n);
        x=fa[top[x]];
        res%=mod;
    }
    if(deep[x]>deep[y]) swap(x,y);
    res+=query(1,dfn[x],dfn[y],1,n);res%=mod;
    return res;
}
void updtree(int x,int d){
    update(1,dfn[x],dfn[x]+dfn[x]+siz[x]-1,1,n,d);
}
int qrytree(int x){
    return query(1,dfn[x],dfn[x]+dfn[x]+siz[x]-1,1,n);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>r>>mod;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        add(u,v);add(v,u);
    }
    dfs1(r,0);dfs2(r,r);build(1,1,n);
    while(m--){
        int op;cin>>op;
        if(op==1){
            int x,y,d;cin>>x>>y>>d;
            updline(x,y,d);
        }
        if(op==2){
            int x,y;cin>>x>>y;
            cout<<qryline(x,y)<<'\n';
        }
        if(op==3){
            int x,d;cin>>x>>d;
            updtree(x,d);
        }
        if(op==4){
            int x;cin>>x;
            cout<<qrytree(x)<<'\n';
        }
    }
    return 0;
}