萌新树剖板子TLE#8#9#10求调，玄关

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int sum[4*N],size[N],dp[N],son[N],f[N],sg[N],re[N],v[N],top[N],lz[N];
vector<int>G[N];
int n,m,r,q;
void dfs1(int u){
    int mx=0;
    size[u]=1;
    for(auto v:G[u]){
        if(v==f[u])continue;
        f[v]=u,dp[v]=dp[u]+1;
        dfs1(v);
        size[u]+=size[v];
        if(son[u]==0||size[v]>size[son[u]])son[u]=v;
    }
}
void dfs2(int u){
    sg[u]=++sg[0],re[sg[u]]=u;
    if(son[u]){
        int v=son[u];
        top[v]=top[u];
        dfs2(v);
    }
    for(auto v:G[u]){
        if(v!=son[u]&&v!=f[u]){
            top[v]=v;
            dfs2(v);
        }
    }
}
void push_down(int v,int l,int r){
    int mid=(l+r)/2;
    lz[v*2+1]+=lz[v],lz[v*2]+=lz[v];
    sum[v*2]+=(mid-l+1)*lz[v],sum[v*2+1]+=lz[v]*(r-mid);
    sum[v]%=q,sum[v*2]%=q,sum[v*2+1]%=q;
    lz[v*2]%=q,lz[v*2+1]%=q;
    lz[v]=0;
}
void add(int l,int r,int x,int y,int v,int p){
    if(l>y||r<x)return;
    if(x<=l&&y>=r){sum[v]+=(r-l+1)*p,lz[v]+=p;return;}
    int mid=(l+r)/2;
    push_down(v,l,r);
    add(l,mid,x,y,v*2,p);
    add(mid+1,r,x,y,v*2+1,p);
    sum[v]=sum[v*2]+sum[v*2+1];
}
int query(int l,int r,int x,int y,int v){
    if(l>y||r<x)return 0;
    if(l>=x&&y>=r)return sum[v];
    push_down(v,l,r);
    int mid=(l+r)/2;
    return (query(l,mid,x,y,v*2)+query(mid+1,r,x,y,v*2+1))%q;
}
void mf(int x,int y,int z){
    int fx=top[x],fy=top[y]; 
    while(fx!=fy){
        if(dp[fx]<dp[fy])swap(x,y),swap(fx,fy);
        add(1,n,sg[fx],sg[x],1,z);
        x=f[fx],fx=top[x];
    }
    if(dp[x]>dp[y])swap(x,y);
    add(1,n,sg[x],sg[y],1,z);
}
int qry(int x,int y){
    int ans=0,fx=top[x],fy=top[y];
    while(fx!=fy){
        if(dp[fx]<dp[fy])swap(x,y),swap(fx,fy);
        ans+=query(1,n,sg[fx],sg[x],1),ans%=q;
        x=f[fx],fx=top[x];
    }
    if(dp[x]>dp[y])swap(x,y);
    ans+=query(1,n,sg[x],sg[y],1),ans%=q;
    return ans;
}
void mdf(int x,int z){
    add(1,n,sg[x],sg[x]+size[x]-1,1,z);
}
int qy(int x){
    return query(1,n,sg[x],sg[x]+size[x]-1,1)%q;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&r,&q);
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        G[x].push_back(y),G[y].push_back(x);
    }
    top[r]=r;
    dfs1(r);
    dfs2(r);
    for(int i=1;i<=n;i++)add(1,n,sg[i],sg[i],1,v[i]);
    for(int i=1;i<=m;i++){
        int k,x,y,z;
        scanf("%d",&k);
        if(k==1){
            scanf("%d%d%d",&x,&y,&z);
            mf(x,y,z);
        }else if(k==2){
            scanf("%d%d",&x,&y);
            printf("%d\n",qry(x,y));
        }else if(k==3){
            scanf("%d%d",&x,&z);
            mdf(x,z);
        }else{
            scanf("%d",&x);
            printf("%d\n",qy(x));
        }
    }
    return 0;
}