63pts 3*Mle+1Wa求调 本地过拍

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,r;
int siz[N],dep[N],hson[N],dfn[N],rnk[N],top[N],f[N],w_dot[N],tot;//size子树大小，dep深度,rnk[den[x]]=x
int nxt[N],to[N],head[N],cnt;//edge
long long p,d[8*N],tag[8*N];
void add(int u,int v){
    nxt[++cnt]=head[u];
    head[u]=cnt;
    to[cnt]=v;
}
void runin(){
    cin>>n>>m>>r>>p;
    for(int i=1;i<=n;i++) cin>>w_dot[i];
    for(int i=n-1;i;i--){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
        //cout<<1<<endl;
    }
}
void dfs1(int x){
    siz[x]=1;
    dep[x]=dep[f[x]]+1;
    for(int i=head[x];i;i=nxt[i]){
        if(to[i]==f[x]) continue;
        f[to[i]]=x;
        dfs1(to[i]);
        siz[x]+=siz[to[i]];
        if(siz[to[i]]>siz[hson[x]]) hson[x]=to[i];
    }
    //cout<<"x="<<x<<" "<<hson[x]<<endl;
    return;
}
void dfs2(int x,int t){
    top[x]=t;
    dfn[x]=++tot;
    rnk[tot]=x;
    dep[x]=dep[f[x]]+1;
    if(hson[x]) dfs2(hson[x],t);
    for(int i=head[x];i;i=nxt[i]){
        if(to[i]==f[x]||to[i]==hson[x]) continue;
       // cout<<to[i]<<endl;
        dfs2(to[i],to[i]);
    }
    //cout<<"dfs2:"<<x<<" dfn="<<dfn[x]<<" top="<<top[x]<<" dep="<<dep[x]<<"siz="<<siz[x]<<endl;
    return;
}
long long query(int o,int x,int y,int l,int r){//求[x,y],现在到了[l,r]
    if(x==l&&y==r)
    return d[o];
    int mid=(l+r)>>1;
    if(tag[o]){
        d[o<<1]+=(mid-l+1)*tag[o];
        d[o<<1]%=p;
        d[o<<1|1]+=(r-mid)*tag[o];
        d[o<<1|1]%=p;
        tag[o<<1]+=tag[o];
        tag[o<<1|1]+=tag[o];
        tag[o]=0;
    }
    if(mid>=y) return query(o<<1,x,y,l,mid);
    else if(mid<x) return query(o<<1|1,x,y,mid+1,r);
    else return (query(o<<1,x,mid,l,mid)+query(o<<1|1,mid+1,y,mid+1,r))%p;
}
void update(int o,int x,int y,int l,int r,int w){
//  cout<<x<<" "<<y<<" "<<l<<" "<<r<<endl;
    d[o]+=(y-x+1)*w;
    d[o]%=p;
    //cout<<x<<" "<<y<<" "<<r<<" "<<l<<endl;
    if(x==l&&y==r){
        tag[o]=(tag[o]+w)%p;
        return;
    }
    int mid=(l+r)>>1;
    if(tag[o]){
        d[o<<1]+=(mid-l+1)*tag[o];
        d[o<<1]%=p;
        d[o<<1|1]+=(r-mid)*tag[o];
        d[o<<1|1]%=p;
        tag[o<<1]+=tag[o];
        tag[o<<1|1]+=tag[o];
        tag[o]=0;
    }
    if(mid>=y) update(o<<1,x,y,l,mid,w);
    else if(mid<x) update(o<<1|1,x,y,mid+1,r,w);
    else update(o<<1,x,mid,l,mid,w),update(o<<1|1,mid+1,y,mid+1,r,w);
    return;
}
void build_tree(int o,int l,int r){
    if(l==r){
        d[o]=w_dot[rnk[l]];
      //  cout<<"rnk="<<rnk[l]<<"l="<<l<<" r="<<r<<" d="<<d[o]<<endl;
        return;
    }
    int mid=(l+r)>>1;
    build_tree(o<<1,l,mid);
    build_tree(o<<1|1,mid+1,r);
    d[o]=(d[o<<1]+d[o<<1|1])%p;
  //  cout<<"l="<<l<<" r="<<r<<" d="<<d[o]<<endl;
    return;
}
long long road_sum(int x,int y){
    long long ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ans+=query(1,dfn[top[x]],dfn[x],1,n);
     //   cout<<"x="<<x<<"l="<<top[x]<<" r="<<dfn[x]<<endl;
        ans%=p;
        x=f[top[x]];
    }
  //  cout<<"ans1="<<ans<<endl;
    if(dfn[x]>dfn[y]) swap(x,y);
    ans+=query(1,dfn[x],dfn[y],1,n);
    ans%=p;
    return ans;
}
inline void road_add(int x,int y,int w){
//  cout<<x<<"  "<<y<<"  "<<top[x]<<"  "<<top[y];
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        update(1,dfn[top[x]],dfn[x],1,n,w);
        x=f[top[x]];
      //  cout<<"x="<<x<<"y="<<y<<endl;
    }
    if(dfn[x]>dfn[y]) swap(x,y);
   // cout<<x<<" "<<y<<" ;"<<dfn[x]<<" "<<dfn[y]<<endl;
    update(1,dfn[x],dfn[y],1,n,w);
}
int main(){
//  freopen("date.in","r",stdin);
    ios::sync_with_stdio(false);
    runin();
    f[r]=0;
    dfs1(r);
    dfs2(r,r);
//    for(int i=1;i<=n;i++){
//      cout<<f[i];
//  }
//  cout<<" f"<<endl;
    build_tree(1,1,n);
    for(int i=m;i;i--){
        int k,x,y,z;
        cin>>k;
        if(k==1){
            cin>>x>>y>>z;
            road_add(x,y,z);
        }
        else if(k==2){
            cin>>x>>y;
            cout<<road_sum(x,y)<<endl;
        }
        else if(k==3){
            cin>>x>>z;
            update(1,dfn[x],dfn[x]+siz[x]-1,1,n,z);
        }
        else{
            cin>>x;
            cout<<query(1,dfn[x],dfn[x]+siz[x]-1,1,n)<<endl;
        }
       // cout<<"1"<<endl;
   // cout<<"son7="<<query(1,dfn[7],dfn[7]+siz[7]-1,1,n)<<endl;
    }
//  cout<<"111";
    return 0;
}