RT，数组应该是开够了的……

但是有8个点RE了……

不知道哪写错了……

#include<bits/stdc++.h>
using namespace std;

long long cnt,sum[8000001];
long long head[8000001];
long long k[8000001];
long long father[8000001];
long long deep[8000001];
long long top[8000001];
long long size[8000001];
long long dfs_order[8000001];
long long sonv[8000001];
long long dfs_clock;
long long fan[8000001];
long long l_tag[8000001];
int n,m,r,p;
int c,x,y,z;

struct node{
    int to;
    int next;
}edge[8000001];

void add(int u,int v){
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs_1(int now,int from,int dep){
    deep[now]=dep;
    father[now]=from;
    size[now]=1;
    for(register int i=head[now];i!=0;i=edge[i].next){

            int to=edge[i].to;

            if(to==from){
                continue;
            }
            dfs_1(to,now,dep+1);
            size[now]+=size[to];
            if(size[to]>size[sonv[now]]){
                sonv[now]=to;
            }
    }
}

void dfs_2(int now,int ding){
    top[now]=ding;
    dfs_order[now]=++dfs_clock;
    fan[dfs_clock]=now;
    if(sonv[now]==0){
        return;
    }
    dfs_2(sonv[now],ding); 
    for(register int i=head[now];i!=0;i=edge[i].next){
        int to=edge[i].to;
        if(to!=father[now]&&to!=sonv[now]){
            dfs_2(to,to);
        }
     }
}

void pushdown(int cur,int lnum,int rnum){
    if(l_tag[cur]==0){
        return;
    }
    l_tag[cur<<1]=(l_tag[cur<<1]+l_tag[cur])%p;
    l_tag[cur<<1|1]=(l_tag[cur<<1|1]+l_tag[cur])%p;
    sum[cur<<1]=(sum[cur<<1]+l_tag[cur])%p;
    sum[cur<<1|1]=(sum[cur<<1|1]+l_tag[cur])%p;
    l_tag[cur]=0;
}

void buildtree(int l,int r,int cur){
     if(l==r){
        sum[cur]=k[fan[l]];
        return;
     }

     int mid=(l+r)>>1;

     buildtree(l,mid,cur<<1);
     buildtree(mid+1,r,cur<<1|1);
     sum[cur]=sum[cur<<1]+sum[cur<<1|1];
}

void updata(int l,int r,int L,int R,int cost,int cur){
     if(L<=l&&r<=R){
        l_tag[cur]=(l_tag[cur]+cost)%p;
        sum[cur]=(sum[cur]+(r-l+1)*cost)%p;
        return;
     }

     int mid=(l+r)>>1;

     pushdown(cur,mid-l+1,r-mid);
     if(L<=mid)updata(l,mid,L,R,cost,cur<<1);
     if(R>=mid+1)updata(mid+1,r,L,R,cost,cur<<1|1);
     sum[cur]=sum[cur<<1]+sum[cur<<1|1];
}

long long query(int l,int r,int L,int R,int cur){
    if(L<=l&&r<=R){
        return sum[cur]%p;
    }
    int mid=(l+r)>>1;
    long long he=0;

    pushdown(cur,mid-l+1,r-mid);
    if(L<=mid){
        he=he+query(l,mid,L,R,cur<<1);
    }
    if(R>=mid+1){
        he=he+query(mid+1,r,L,R,cur<<1|1);
    }
    return he%p;
}

void updata_l(int x,int y,int cost){
    while(top[x]!=top[y]){
        if(deep[x]>=deep[y]){
            updata(1,n,dfs_order[top[x]],dfs_order[x],cost,1);
            x=top[x];x=father[x];
        }
        else{
            updata(1,n,dfs_order[top[y]],dfs_order[y],cost,1);
            y=top[y];y=father[y]; 
        }
     }
    if(dfs_order[x]<dfs_order[y]){
        updata(1,n,dfs_order[x],dfs_order[y],cost,1);
    } 
    else{
        updata(1,n,dfs_order[y],dfs_order[x],cost,1);
    }
}

long long query_l(int x,int y){
    long long answer=0;
    while(top[x]!=top[y]){
        if(deep[x]>=deep[y]){
            answer=(answer+query(1,n,dfs_order[top[x]],dfs_order[x],1))%p;
            x=top[x];x=father[x];
        }
        else{
            answer=(answer+query(1,n,dfs_order[top[y]],dfs_order[y],1))%p;
            y=top[y];y=father[y];
        }
    }
    if(dfs_order[x]<dfs_order[y])answer=(answer+query(1,n,dfs_order[x],dfs_order[y],1))%p;
    else answer=(answer+query(1,n,dfs_order[y],dfs_order[x],1))%p;
    return answer%p;
}

int main(){
    scanf("%d%d%d%d",&n,&m,&r,&p);
    for(register int i=1;i<=n;i++){
        scanf("%d",&k[i]);
    }
    for(register int i=1;i<=n-1;i++){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs_1(r,0,1);
    dfs_2(r,r);
    buildtree(1,n,1);
    for(register int i=1;i<=m;i++){
        scanf("%d",&c);
        if(c==1){
            scanf("%d%d%d",&x,&y,&z);
            updata_l(x,y,z);
        }
        if(c==2){
            scanf("%d%d",&x,&y);
            printf("%lld\n",query_l(x,y));
        }
        if(c==3){
            scanf("%d%d",&x,&y);
            updata(1,n,dfs_order[x],dfs_order[x]+size[x]-1,y,1);
        }
        if(c==4){
            scanf("%d",&x);
            printf("%lld\n",query(1,n,dfs_order[x],dfs_order[x]+size[x]-1,1));   
        }
    }
    return 0;
}