重链剖分19pts求调！！！

评测记录：https://www.luogu.com.cn/record/191034627

代码：

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define inf 0x3f3f3f3f3f3f3f3f
#define LOCAL
using namespace std;
mt19937 qwq(chrono::steady_clock::now().time_since_epoch().count());
#define rd(n) uniform_int_distribution<int>(1,n)(qwq)
#define rddb(n) uniform_real_distribution<double>(1,n)(qwq)
namespace ly{
    namespace IO{
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar()(p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush()(fwrite(out,1,p3-out,stdout))
            #define putchar(x)(p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
            namespace usr{
                template<typename type>
                inline type read(type&x){
                    x=0;bool flag(0);char ch=getchar();
                    while(!isdigit(ch))flag^=ch=='-',ch=getchar();
                    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                    return flag?x=-x:x;
                }
                template<typename type>
                inline void write(type x){
                    x<0?x=-x,putchar('-'):0;
                    static short Stack[50],top(0);
                    do Stack[++top]=x%10,x/=10;while(x);
                    while(top)putchar(Stack[top--]|48);
                }
                inline char read(char&x){do x=getchar();while(isspace(x));return x;}
                inline char write(const char&x){return putchar(x);}
                inline void read(char*x){static char ch;read(ch);do*(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
                template<typename type>inline void write(type*x){while(*x)putchar(*(x++));}
                inline void read(string&x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
                inline void write(const string&x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
                template<typename type,typename...T>inline void read(type&x,T&...y){read(x),read(y...);}
                template<typename type,typename...T>
                inline void write(const type&x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
                template<typename type>
                inline void put(const type&x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
            }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }
    using namespace IO::usr;
}
using namespace ly::IO::usr;
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid(l,r) ((l+r)>>1)
int n,m,r,mod,a[100010],opt,x,y,z,head[100010],nxt[200010],to[200010],cnt,dep[100010],siz[100010],zs[100010],fa[100010],dfn[100010],cnt2,zfa[100010],a2[100010],tr[400010],lazy[400010];
void add(int x,int y){
    nxt[++cnt]=head[x];
    to[cnt]=y;
    head[x]=cnt;
}
void dfs1(int x,int f){
    dep[x]=dep[f]+1;
    siz[x]=1;
    fa[x]=f;
    int maxx=-1;
    for(int i=head[x];i!=-1;i=nxt[i]){
        int y=to[i];
        if(y==f)continue;
        dfs1(y,x);
        siz[x]+=siz[y];
        if(siz[y]>maxx)maxx=siz[y],zs[x]=y;
    }
}
void dfs2(int x,int zf){
    dfn[x]=++cnt2;
    zfa[x]=zf;
    a2[cnt2]=a[x];
    if(zs[x])dfs2(zs[x],zf);
    for(int i=head[x];i!=-1;i=nxt[i]){
        int y=to[i];
        if(y==fa[x]||y==zs[x])continue;
        dfs2(y,y);
    }
}
void pushup(int p){
    tr[p]=(tr[ls(p)]+tr[rs(p)])%mod;
}
void pushdown(int l,int r,int p){
    if(lazy[p]){
        lazy[ls(p)]=(lazy[p]+lazy[ls(p)])%mod;
        lazy[rs(p)]=(lazy[p]+lazy[rs(p)])%mod;
        a[ls(p)]=(a[ls(p)]+lazy[p]*(mid(l,r)-l+1))%mod;
        a[rs(p)]=(a[rs(p)]+lazy[p]*(r-mid(l,r)))%mod;
        lazy[p]=0;
    }
}
void build(int l,int r,int p){
    if(l==r){
        tr[p]=a2[l]%mod;
        return;
    }
    build(l,mid(l,r),ls(p));
    build(mid(l,r)+1,r,rs(p));
    pushup(p);
}
void update2(int l,int r,int L,int R,int p,int k){
    if(L<=l&&R>=r){
        tr[p]=(tr[p]+k*(r-l+1))%mod;
        lazy[p]+=k;
        return;
    }
    pushdown(l,r,p);
    if(L<=mid(l,r))update2(l,mid(l,r),L,R,ls(p),k);
    if(R>mid(l,r))update2(mid(l,r)+1,r,L,R,rs(p),k);
    pushup(p);
}
void update(int x,int y,int k){
    k%=mod;
    while(zfa[x]!=zfa[y]){
        if(dep[zfa[x]]<dep[zfa[y]])swap(x,y);
        update2(1,n,dfn[zfa[x]],dfn[x],1,k);
        x=fa[zfa[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update2(1,n,dfn[x],dfn[y],1,k);
}
int query2(int l,int r,int L,int R,int p){
    if(L<=l&&R>=r){
        return tr[p]%mod;
    }
    int ans=0;
    pushdown(l,r,p);
    if(L<=mid(l,r))ans+=query2(l,mid(l,r),L,R,ls(p));
    if(R>mid(l,r))ans+=query2(mid(l,r)+1,r,L,R,rs(p));
    return ans%mod;
}
int query(int x,int y){
    int sum=0;
    while(zfa[x]!=zfa[y]){
        if(dep[zfa[x]]<dep[zfa[y]])swap(x,y);
        sum+=query2(1,n,dfn[zfa[x]],dfn[x],1);
        sum%=mod;
        x=fa[zfa[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    sum=(sum+query2(1,n,dfn[x],dfn[y],1))%mod;
    return sum;
}
signed main(){
    memset(head,-1,sizeof(head));
    read(n,m,r,mod);
    for(int i=1;i<=n;i++)read(a[i]);
    for(int i=1;i<n;i++){
        read(x,y);
        add(x,y);
        add(y,x);
    }
    dfs1(r,0);
    dfs2(r,r);
    build(1,n,1);
    while(m--){
        read(opt,x);
        if(opt==1){
            read(y,z);
            update(x,y,z);
        }
        if(opt==2){
            read(y);
            put(query(x,y));
        }
        if(opt==3){
            read(z);
            update2(1,n,dfn[x],dfn[x]+siz[x]-1,1,z%mod);
        }
        if(opt==4){
            put(query2(1,n,dfn[x],dfn[x]+siz[x]-1,1));
        }
    }
    return 0;
}