重链板子求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int arr[N];
int dep[N];
int dfn[N];
int size[N];
int fa[N];
int wc[N];
int rdfn[N];
int top[N];
int mod;
int n,m,r;
int vs=0;
vector<int>v[N];
struct sd {
    int l,r;
    int val;
    int lazytag;
} T[4*N];
void dfs1(int u,int f) {
    fa[u]=f;
    size[u]=1;
    dep[u]=dep[f]+1;
    for(int i=0; i<v[u].size(); i++) {
        int k=v[u][i];
        if(k==f)continue;
        dfs1(k,u);
        size[u]+=size[k];
        if(size[k]>size[wc[u]])wc[u]=k;
    }

}
void dfs2(int u,int Top) {
    dfn[u]=++vs;
    rdfn[vs]=u;
    top[u]=Top;
    if(wc[u]!=0) {
        dfs2(wc[u],Top);
        for(int i=0; i<v[u].size(); i++) {
            if(v[u][i]!=fa[u]&&v[u][i]!=wc[u])dfs2(v[u][i],v[u][i]);
        }
    }
    else return ;
}
bool IR(int L,int R,int l,int r) {
    return l<=L&&R<=r;
}
bool OR(int L,int R,int l,int r) {
    return L>r||R<l;
}
void maketag(int cnt,int len,int data) {
    T[cnt].lazytag +=data;
    T[cnt].val +=len*data%mod;
    T[cnt].lazytag %=mod;
    T[cnt].val %=mod;
}
void pushup(int cnt) {
    T[cnt].val =(T[cnt*2].val +T[cnt*2+1].val)%mod;
}
void pushdown(int l,int r,int cnt)
{
    int mid=(l+r)/2;
    maketag(cnt*2,mid-l+1,T[cnt].lazytag );
    maketag(cnt*2+1,r-mid,T[cnt].lazytag );
    T[cnt].lazytag =0;
}
void update(int L,int R,int l,int r,int cnt,int data) {
    if(IR(L,R,l,r)) {
        maketag(cnt,r-l+1,data);
    } else if(!(OR(L,R,l,r))) {
        int mid=(L+R)/2;
        pushdown(L,R,cnt);
        update(L,mid,l,r,cnt*2,data);
        update(mid+1, R, l, r, cnt*2+1, data);
        pushup( cnt);
    }
}
void build(int l,int r,int cnt) {
    if(l==r) {
        T[cnt].val=arr[rdfn[l]];
        T[cnt].l =l;
        T[cnt].r =r;
        return ;
    }
    int mid=(l+r)/2;
    build(l,mid,cnt*2);
    build(mid+1,r,cnt*2+1);
    pushup(cnt);
}
int q1(int L,int R,int l,int r,int cnt){
    if(IR(L,R,l,r)){
        return T[cnt].val%mod ;
    }else if(!OR(L,R,l,r)){
        int mid=(L+R)/2;
        pushdown(L,R,cnt);
        return (q1(L,mid,l,r,cnt*2)+q1(mid+1,R,l,r,cnt*2+1))%mod;
    }else return 0;
}
void upd(int x,int y,int z) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,n,dfn[top[x]],dfn[x],1,z);
        x=fa[top[x]];
    }
    update(1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),1,z);
}
int q(int x,int y) {
    int ans=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        ans+=q1(1,n,dfn[top[x]],dfn[x],1);
        ans%=mod;
        x=fa[top[x]];
    }
     ans+=q1(1,n,min(dfn[x],dfn[y]),max(dfn[x],dfn[y]),1);
     return ans%mod;
}
signed main() {
//  freopen("qwq.in","r",stdin);
//  freopen("me.out","w",stdout);
    cin >> n >> m >> r >> mod;
    for(int i=1; i<=n; i++) {
        cin >> arr[i];
    }
    for(int i=1; i<n; i++) {
        int x,y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs1(r,0);
    dfs2(r,r);
    build(1,n,1);
    for(int i=1; i<=m; i++) {
        int flag;
        cin >> flag;
        if(flag==1) {
            int x,y,z;
            cin >> x >> y >> z;
            upd(x,y,z);
        }
        if(flag==2) {
            int x,y;
            cin >> x >> y;
            cout << q(x,y)%mod;
            puts("");
        }
        if(flag==3) {
            int x,y;
            update(1,n,dfn[x],dfn[x]+size[x]-1,1,y);
        }
        if(flag==4){
            int x;
            cin >> x;
            cout << q1(1,n,dfn[x],dfn[x]+size[x]-1,1)%mod;
            puts("");
        }       

    }
//  debug();
    return 0;
}