19pts,AC#1#11,3TLE,其余WA

#include<bits/stdc++.h>
#define int long long

using namespace std;

int n,m,mod;
struct tree {
    int r,num[100010],h[100010],e[200010][2],cnt;
    int muc[100010],dep[100010],son[100010],nbh[100010],cntn,top[100010],fat[100010];
    void add(int x,int y) {
        e[++cnt][0]=y;
        e[cnt][1]=h[x];
        h[x]=cnt;
        e[++cnt][0]=x;
        e[cnt][1]=h[y];
        h[y]=cnt;
    }
    void init(int p,int f) {
        muc[p]=1;
        int ma=0;
        for(register int i=h[p]; i; i=e[i][1])
            if(e[i][0]!=f) {
                init(e[i][0],p);
                muc[p]+=muc[e[i][0]];
                if(muc[e[i][0]]>ma)
                    ma=muc[e[i][0]],son[p]=e[i][0];
            }
    }
    void reset(int p,int f) {
        nbh[p]=++cntn;
        if(son[p])
            reset(son[p],p);
        for(register int i=h[p]; i; i=e[i][1])
            if(e[i][0]!=f&&e[i][0]!=son[p]) {
                reset(e[i][0],p);
            }
    }
    void reinit(int p,int f) {
        fat[nbh[p]]=nbh[f],dep[nbh[p]]=dep[nbh[f]]+1,muc[nbh[p]]=1;
        if(!top[nbh[p]])
            top[nbh[p]]=nbh[p];
        if(son[p])
            reinit(son[p],p),muc[nbh[p]]+=muc[nbh[son[p]]],top[nbh[son[p]]]=top[nbh[p]];
        for(register int i=h[p]; i; i=e[i][1])
            if(e[i][0]!=f&&e[i][0]!=son[p]) {
                reinit(e[i][0],p);
                muc[nbh[p]]+=muc[nbh[e[i][0]]];
            }
    }
} tree;
struct xds {
    int num[100010],l[400010],r[400010],v[400010],tag[400010];
    void build(int p,int lef,int rig) {
        l[p]=lef,r[p]=rig;
        if(lef==rig)
            v[p]=num[lef]%mod;
        else {
            build(p*2,lef,(lef+rig)/2);
            build(p*2+1,(lef+rig)/2+1,rig);
            v[p]=v[p*2]+v[p*2+1],v[p]%=mod;
        }
    }
    void down(int p) {
        tag[p*2]+=tag[p],tag[p*2+1]+=tag[p];
        tag[p*2]%=mod,tag[p*2+1]%=mod;
        v[p*2]+=tag[p]*(r[p*2]-l[p*2]+1),v[p*2+1]+=tag[p]*(r[p*2+1]-l[p*2+1]+1);
        v[p*2]%=mod,v[p*2+1]%=mod;
        tag[p]=0;
    }
    int que(int p,int lef,int rig) {
        if(lef<=l[p]&&rig>=r[p])
            return v[p]%mod;
        down(p);
        int ret=0;
        if(lef<=(l[p]+r[p])/2)
            ret+=que(p*2,lef,rig);
        if(rig>(l[p]+r[p])/2)
            ret+=que(p*2+1,lef,rig);
        return ret%mod;
    }
    void cha(int p,int lef,int rig,int k) {
        if(lef<=l[p]&&rig>=r[p]) {
            tag[p]+=k,tag[p]%=mod;
            v[p]+=k*(r[p]-l[p]+1),v[p]%=mod;
        } else {
            down(p);
            if(lef<=(l[p]+r[p])/2)
                cha(p*2,lef,rig,k);
            if(rig>(l[p]+r[p])/2)
                cha(p*2+1,lef,rig,k);
            v[p]=v[p*2]+v[p*2+1],v[p]%=mod;
        }
    }
} all;

inline int read() {
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        f=(ch=='-'?-1:f),ch=getchar();
    while(ch>='0'&&ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f*x;
}

signed main() {
    n=read(),m=read(),tree.r=read(),mod=read();
    for(register int i=1; i<=n; i++)
        tree.num[i]=read()%mod;
    for(register int i=1; i<n; i++)
        tree.add(read(),read());
    tree.init(tree.r,0);
    tree.reset(tree.r,0);
    tree.reinit(tree.r,0);
    for(register int i=1; i<=n; i++)
        all.num[tree.nbh[i]]=tree.num[i];
    all.build(1,1,n);
    while(m--) {
        int op=read();
        if(op==1) {
            int x=tree.nbh[read()],y=tree.nbh[read()],z=read()%mod;
            while(tree.top[x]!=tree.top[y]) {
                if(tree.dep[tree.top[x]]<tree.dep[tree.top[y]])
                    swap(x,y);
                all.cha(1,tree.top[x],x,z);
                x=tree.fat[tree.top[x]];
            }
            if(tree.dep[x]>tree.dep[y])
                swap(x,y);
            all.cha(1,x,y,z);
        }
        if(op==2) {
            int x=tree.nbh[read()],y=tree.nbh[read()];
            int ans=0;
            while(tree.top[x]!=tree.top[y]) {
                if(tree.dep[tree.top[x]]<tree.dep[tree.top[y]])
                    swap(x,y);
                ans+=all.que(1,tree.top[x],x),ans%=mod;
                x=tree.fat[tree.top[x]];
            }
            if(tree.dep[x]<tree.dep[y])
                swap(x,y);
            ans+=all.que(1,x,y);
            printf("%lld\n",ans%mod);
        }
        if(op==3) {
            int x=tree.nbh[read()],z=read()%mod;
            all.cha(1,x,x+tree.muc[x]-1,z);
        }
        if(op==4) {
            int x=tree.nbh[read()];
            printf("%lld\n",all.que(1,x,x+tree.muc[x]-1));
        }
    }
}