RE on #9 求调

#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
#define maxn 1000001
#define lp p<<1
#define rp p<<1|1
using namespace std;
vector<int>e[maxn];
int n,m,st,mod,cnt,val[maxn],top[maxn],fa[maxn],son[maxn],dep[maxn],size[maxn],mygo[maxn],back[maxn],d[maxn<<2],lz[maxn<<2];
void add(int u,int v){
    e[u].push_back(v);
}
void dfs1(int p,int father){
    size[p]=1;
    fa[p]=father;
    dep[p]=dep[father]+1;
    for(auto q:e[p]){
        if(q==father) continue;
        fa[q]=p;
        dfs1(q,p);
        size[p]+=size[q];
        size[p]%=mod;
        if(size[q]>size[son[p]]) son[p]=q;
    }
}
void dfs2(int p){
    cnt++;
    mygo[p]=cnt;
    back[cnt]=val[p]%mod;
    for(auto q:e[p]){
        if(q==fa[p]) continue;
        if(q==son[p]) top[q]=top[p];
        else top[q]=q;
        dfs2(q);
    }
}
void build(int l,int r,int p){
    if(l==r){
        d[p]=back[l];
        return;
    }
    int mid=l+r>>1;
    build(l,mid,lp);
    build(mid+1,r,rp);
    d[p]=d[lp]+d[rp];
    d[p]%=mod;
}
void push(int l,int r,int p,int k){
    d[p]+=(r-l+1)*k%mod;
    d[p]%=mod;
    lz[p]+=k;
    lz[p]%=mod;
}
void del(int l,int r,int p){
    if(lz[p]&&l!=r){
        int mid=l+r>>1;
        push(l,mid,lp,lz[p]);
        push(mid+1,r,rp,lz[p]);
        lz[p]=0;
    }
}
void add(int s,int t,int l,int r,int p,int k){
    if(s<=l&&r<=t){
        push(l,r,p,k);
        return;
    }
    int mid=l+r>>1;
    del(l,r,p);
    if(s<=mid) add(s,t,l,mid,lp,k);
    if(t>mid)  add(s,t,mid+1,r,rp,k);
    d[p]=d[lp]+d[rp];
    d[p]%=mod;
}
int get(int s,int t,int l,int r,int p){
    if(s<=l&&r<=t) return d[p]%mod;
    int mid=l+r>>1;
    del(l,r,p);
    int sum=0;
    if(s<=mid) sum+=get(s,t,l,mid,lp);
    if(t>mid)  sum+=get(s,t,mid+1,r,rp);
    return sum%mod;
}
void tree_add(int u,int v,int w){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        add(mygo[top[u]],mygo[u],1,n,1,w);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    add(mygo[u],mygo[v],1,n,1,w);
}
int tree_sum(int u,int v){
    int sum=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        sum+=get(mygo[top[u]],mygo[u],1,n,1);
        sum%=mod;
        u=fa[top[u]];
    }
    if(dep[u]>dep[v]) swap(u,v);
    sum+=get(mygo[u],mygo[v],1,n,1);
    sum%=mod;
    return sum;
}
void node_add(int u,int w){
    add(mygo[u],mygo[u]+size[u]-1,1,n,1,w);
}
int node_sum(int u){
    return get(mygo[u],mygo[u]+size[u]-1,1,n,1);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int i,op,u,v,w;
    cin>>n>>m>>st>>mod;
    for(i=1;i<=n;i++) cin>>val[i];
    for(i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs1(st,st);
    dfs2(st);
    build(1,n,1);
    for(i=1;i<=m;i++){
        cin>>op;
        switch(op){
            case(1):{
                cin>>u>>v>>w;
                tree_add(u,v,w%mod);
                break;
            }
            case(2):{
                cin>>u>>v;
                cout<<tree_sum(u,v)<<"\n";
                break;
            }
            case(3):{
                cin>>u>>w;
                node_add(u,w%mod);
                break;
            }
            case(4):{
                cin>>u;
                cout<<node_sum(u)<<"\n";
                break;
            }
        }
    }
}

提交记录