WA,求助

#include<bits/stdc++.h>
using namespace std;
#define ull long long
ull fa[500010];//
ull tp[500010];//
ull dep[500010];//
ull a[500010];//
ull flag[500010];//
ull Siz[500010];//
ull dfn[500010];//
ull fdn[500010];//
ull now;//
ull n,m,R,P;//
struct node{
    ull l,r,tag,sum;
}p[500010];
ull siz(ull x){
    return p[x].r-p[x].l+1;
}
void pushup(ull x){
    p[x].sum=(p[2*x].sum+p[2*x+1].sum)%P;
}
void pushdown(ull x){
    if(!p[x].tag)return;
    ull tag=p[x].tag;
    ull lc=2*x,rc=2*x+1;
    p[lc].sum=(p[lc].sum+tag*siz(lc))%P;
    p[rc].sum=(p[rc].sum+tag*siz(rc))%P;
    p[lc].tag+=tag;
    p[rc].tag+=tag;
    p[lc].tag%=P;
    p[rc].tag%=P;
    p[x].tag=0;
}
void creat(ull x,ull l,ull r){
    if(l>r)swap(l,r);
    p[x].l=l;
    p[x].r=r;
    if(l==r){
        p[x].sum=a[fdn[l]]%P;
        return;
    }
    ull mid=(l+r)/2;
    creat(2*x,l,mid);
    creat(2*x+1,mid+1,r);
    pushup(x);
}
void change(ull x,ull k,ull l,ull r){
    if(l>r)swap(l,r);
    if(p[x].l>r||p[x].r<l)return;
    if(p[x].l>=l&&p[x].r<=r){
        p[x].tag+=k;
        p[x].sum+=k*siz(x);
        p[x].tag%=P;
        p[x].sum%=P;
        return;
    }
    pushdown(x);
    change(2*x,k,l,r);
    change(2*x+1,k,l,r);
    pushup(x);
}
ull query(ull x,ull l,ull r){
    if(l>r)swap(l,r);
    if(p[x].l>r||p[x].r<l)return 0;
    if(l<=p[x].l&&p[x].r<=r){
        return p[x].sum%P;
    }
    pushdown(x);
    return (query(2*x,l,r)+query(2*x+1,l,r))%P;
}
vector<int>e[500010];
void dfs1(int u,int f){
    Siz[u]=1;
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v!=f){
            dfs1(v,u);
            Siz[u]+=Siz[v];
        }
    }
}
void dfs2(int u,int f){
    dfn[u]=++now;
    fdn[now]=u;
    int f1=dfn[f],u1=dfn[u];
    dep[u1]=dep[f1]+1;
    if(!flag[u]){
        tp[u1]=u1;
    }else{
        tp[u1]=tp[f1];
    }
    fa[u1]=f1;
    int mx=0,k=0;
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v!=f&&Siz[v]>mx){
            k=v;
            mx=Siz[v];
        }
    }
    flag[k]=1;
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v!=f){
            dfs2(v,u);
        }
    }
}
int main(){
    cin>>n>>m>>R>>P;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=P;
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(R,0);
    dfs2(R,0);
    creat(1,1,n);
    while(m--){
        int k=0,u=0,v=0,z=0;
        cin>>k>>u;
        if(k==1){
            cin>>v>>z;
        }else if(k==2){
            cin>>v;
        }else if(k==3){
            cin>>z;
        }

        u=dfn[u];
        v=dfn[v];
        z%=P;

        if(k==1){
            while(tp[u]!=tp[v]){
                if(dep[tp[u]]<dep[tp[v]]){
                    swap(u,v);
                }
                change(1,z,tp[u],u);
                u=fa[tp[u]];
            }
            if(dep[u]>dep[v]){
                swap(u,v);
            }
            change(1,z,u,v);
        }
        if(k==2){
            int sum=0;
            while(tp[u]!=tp[v]){
                if(dep[tp[u]]<dep[tp[v]]){
                    swap(u,v);
                }
                sum=(sum+query(1,tp[u],u))%P;
                u=fa[tp[u]];
            }
            if(dep[u]>dep[v]){
                swap(u,v);
            }
            sum=(sum+query(1,u,v))%P;
            cout<<sum<<endl;
        }
        if(k==3){
            change(1,z,u,u+Siz[fdn[u]]-1);
        }
        if(k==4){
            cout<<query(1,u,u+Siz[fdn[u]]-1)<<endl;
        }
    }
    return 0;
}

rt,提交记录

悬赏1关注