树剖板子 WA 37pts求助

rt,WA #4~#10

线段树测了没问题

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define pii pair<int,int>
#define mp make_pair
vector<int>e[200020];
struct node{
  int pre,dep,son,top,siz;
  int val,dfn,idx;
  node(void){
      pre=son=top=-1;
      val=dep=0;
      dfn=idx=-1;
      siz=1;
  }
}a[200020];
int cnt=0;
void dfs1(int x,int pre){
    a[x].pre=pre;
    a[x].dep=a[pre].dep+1;
    for(auto i:e[x]){
        if(i==pre)continue;
        dfs1(i,x);
        a[x].siz+=a[i].siz;
        if(a[x].son==-1)a[x].son=i;
        else if(a[a[x].son].siz<a[i].siz)a[x].son=i;
    }
}
void dfs2(int x,int top){
    a[x].top=top;
    a[x].dfn=++cnt;
    a[cnt].idx=x;
    if(a[x].son!=-1)dfs2(a[x].son,top);
    for(auto i:e[x]){
        if(i==a[x].pre)continue;
        if(i==a[x].son)continue;
        dfs2(i,i);
    }
}
void Link(int x,int y,vector<pii> &link){
    while(a[x].top!=a[y].top){
        int topx=a[x].top;
        int topy=a[y].top;
        if(a[topx].dep<a[topy].dep){
            link.push_back(mp(a[topy].dfn,a[y].dfn));
            y=a[topy].pre;
        }
        else{
            link.push_back(mp(a[topx].dfn,a[x].dfn));
            x=a[topx].pre;
        }
    }
    if(a[x].dep<a[y].dep){
        link.push_back(mp(a[x].dfn,a[y].dfn));
    }else{
        link.push_back(mp(a[y].dfn,a[x].dfn));
    }
}

int n,m,root,mod;
//namespace Segment_Tree{
#define ls p<<1
#define rs p<<1|1
struct Seg{
    int sum,laz;
  //  int l,r;
  //  int len()const{
 //       return r-l+1;
  //  }
}seg[1000010<<2];
void pushup(int p){
    seg[p].sum=(seg[ls].sum+seg[rs].sum)%mod;
}
void pushdown(int p,int l,int r){
    int mid=(l+r)>>1;
    (seg[ls].sum+=(mid-l+1)*seg[p].laz)%mod;
    (seg[ls].laz+=seg[p].laz)%mod;
    (seg[rs].sum+=(r-mid-0)*seg[p].laz)%mod;
    (seg[rs].laz+=seg[p].laz)%mod;
    seg[p].laz=0;
}
void build(int p,int l,int r){
    if(l==r){
        seg[p].sum=a[a[l].idx].val%mod;
        seg[p].laz=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid+0);
    build(rs,mid+1,r);
    pushup(p);
}
int ask(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return seg[p].sum%mod;
    }
    pushdown(p,l,r);
    int mid=(l+r)>>1,res=0;
    if(L<=mid)(res+=ask(ls,l,mid+0,L,R))%mod;
    if(mid<R) (res+=ask(rs,mid+1,r,L,R))%mod;
    return res;
}
void change(int p,int l,int r,int L,int R,int v){
    if(L<=l&&r<=R){
        (seg[p].sum+=v*(r-l+1))%mod;
        (seg[p].laz+=v)%mod;
        return;
    }
    pushdown(p,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)change(ls,l,mid+0,L,R,v);
    if(mid<R) change(rs,mid+1,r,L,R,v);
    pushup(p);
}
//}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m>>root>>mod;
    for(int i=1;i<=n;i++)cin>>a[i].val;
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs1(root,0);
    dfs2(root,root);
    build(1,1,n);
    while(m--){
        int op,x,y,k;
        cin>>op>>x;
        if(op==1){
            cin>>y>>k;
            vector<pii>link;
            Link(x,y,link);
            for(auto i:link){
                change(1,1,n,i.first,i.second,k);
            }
        }
        if(op==2){
            cin>>y;
            vector<pii>link;
            Link(x,y,link);
            int res=0;
            for(auto i:link){
                (res+=ask(1,1,n,i.first,i.second))%mod;
            }
            cout<<res<<endl;
        }
        if(op==3){
            cin>>k;
            change(1,1,n,a[x].dfn,a[x].dfn+a[x].siz-1,k);
        }
        if(op==4){
            cout<<ask(1,1,n,a[x].dfn,a[x].dfn+a[x].siz-1)%mod<<endl;
        }
    }
    return 0;
}