提交记录https://www.luogu.com.cn/record/169112807

3#11AC（大概是运气过的），#8#9#10MLE，其余WA

代码如下：

#include<bits/stdc++.h>
#define int long long
#define for(i,x,y) for(register int i=x;i<=y;i++)
using namespace std;
inline int read(){
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
const int N=1e5+5;
int n,m,root,mod,opt;
int u,v,cnt,head[N];
int cnt_val[N],ans,res;
struct POINT{
    int id,val,dep,top,fa,heavy_son,size;
}a[N];
struct EDGE{
    int next;
    int to;
}edge[N];
struct node{
    int val;
    int lazy;
}b[N<<2];
void add(int x,int y){
    cnt++;
    edge[cnt]={head[x],y};
    head[x]=cnt;
}
void dfs_1(int x,int father,int depth){
    a[x].dep=depth;
    a[x].fa=father;
    a[x].size=1;
    int maxson=-1;
    int i=head[x];
    while(i){
        int y=edge[i].to;
        if(y==father);
        else{
            dfs_1(y,x,depth+1);
            a[x].size+=a[y].size;
            if(a[y].size>maxson){
                a[x].heavy_son=y;
                maxson=a[y].size;
            }
        }
        i=edge[i].next;
    }
}
void dfs_2(int x,int top){
    cnt++;
    a[x].id=cnt;
    cnt_val[cnt]=a[x].val;
    a[x].top=top;
    if(a[x].heavy_son==0)return;
    dfs_2(a[x].heavy_son,top);
    int i=head[x];
    while(i){
        int y=edge[i].to;
        if(y==a[x].fa||y==a[x].heavy_son);
        else dfs_2(y,y);
        i=edge[i].next;
    }
}
void build_the_tree(int rt,int l,int r){
    if(l==r){
        b[rt].val=cnt_val[l]%mod;
        return;
    }
    int mid=(l+r)>>1;
    build_the_tree(rt*2,l,mid);
    build_the_tree(rt*2+1,mid+1,r);
    b[rt].val=(b[rt*2].val+b[rt*2+1].val)%mod;
}
void pass_the_tree(int rt,int l,int r){
    int mid=(l+r)>>1;
    b[rt*2].lazy=b[rt].lazy;
    b[rt*2].val=(b[rt*2].val+b[rt*2].lazy*(mid-l+1)%mod)%mod;
    b[rt*2+1].lazy=b[rt].lazy;
    b[rt*2+1].val=(b[rt*2+1].val+b[rt*2+1].lazy*(r-mid)%mod)%mod;
    b[rt].lazy=0;
}
void change_the_tree(int rt,int l,int r,int l_should,int r_should,int k){
    if(l>r_should||r<l_should)return;
    else if(l>=l_should&&r<=r_should){
        b[rt].lazy+=k;
        b[rt].val+=k*(r-l+1);
        return;
    }
    else{
        pass_the_tree(rt,l,r);
        int mid=(l+r)>>1;
        change_the_tree(rt*2,l,mid,l_should,r_should,k);
        change_the_tree(rt*2+1,mid+1,r,l_should,r_should,k);
        b[rt].val=(b[rt*2].val+b[rt*2+1].val)%mod;
    }
}
void print_the_tree(int rt,int l,int r,int l_should,int r_should){
    if(l>r_should||r<l_should)return;
    else if(l>=l_should&&r<=r_should){
        res=(res+b[rt].val)%mod;
        return;
    }
    else{
        pass_the_tree(rt,l,r);
        int mid=(l+r)>>1;
        print_the_tree(rt*2,l,mid,l_should,r_should);
        print_the_tree(rt*2+1,mid+1,r,l_should,r_should);
    }
}
signed main(){
    n=read(),m=read(),root=read(),mod=read();
    for(i,1,n)a[i].val=read();
    for(i,1,n-1){
        u=read(),v=read();
        add(u,v);
        add(v,u);
    }
    dfs_1(root,0,1);
    cnt=0;
    dfs_2(root,root);
    build_the_tree(1,1,n);
    for(i,1,m){
        opt=read();
        int x,y,z,temp;
        switch(opt){
            case 1:
                x=read(),y=read(),z=read();
                z%=mod;
                while(a[x].top!=a[y].top){
                    if(a[a[x].top].dep<a[a[y].top].dep)temp=x,x=y,y=temp;
                    change_the_tree(1,1,n,a[a[x].top].id,a[x].id,z);
                    x=a[a[x].top].fa;
                }
                if(a[x].dep>a[y].dep)temp=x,x=y,y=temp;
                change_the_tree(1,1,n,a[x].id,a[y].id,z);
                break;
            case 2:
                x=read(),y=read();
                ans=0;
                while(a[x].top!=a[y].top){
                    if(a[a[x].top].dep<a[a[y].top].dep)temp=x,x=y,y=temp;
                    res=0;
                    print_the_tree(1,1,n,a[a[x].top].id,a[x].id);
                    ans=(ans+res)%mod;
                    x=a[a[x].top].fa;
                }
                if(a[x].dep>a[y].dep)temp=x,x=y,y=temp;
                res=0;
                print_the_tree(1,1,n,a[x].id,a[y].id);
                ans=(ans+res)%mod;
                printf("%lld\n",ans);
                break;
            case 3:
                x=read(),z=read();
                change_the_tree(1,1,n,a[x].id,a[x].id+a[x].size-1,z);
                break;
            case 4:
                x=read();
                res=0;
                print_the_tree(1,1,n,a[x].id,a[x].id+a[x].size-1);
                printf("%lld\n",res%mod);
                break;
        }
    }
    return 0;
}