蒟蒻树剖求条

一半WA还有一半RE求调

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10; 
int n,m,root,P;
int a[N];int top[N];
int son[N];
int dep[N];
int fa[N];
int dfn[N];
int rnk[N];
int siz[N];
int bot[N];
vector<int> g[N]; 
void dfs1(int u)
{
    son[u]=-1;
    siz[u]=1;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(!dep[v])
        {
            dep[v]=dep[u]+1;
            fa[v]=u;
            dfs1(v);
            siz[u]+=siz[v];
            if(son[u]==-1||siz[v]>siz[v])son[u]=v;
        }
    }
}
int cnt;
void dfs2(int u,int t)
{
    top[u]=t;
    dfn[u]=++cnt;
    bot[u]=cnt;
    rnk[cnt]=u;
    if(son[u]!=-1)  dfs2(son[u],t);
    cout<<u<<endl;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(v!=fa[u]&&v!=son[u]){
            dfs2(v,v);
            bot[u]=max(bot[v],bot[u]);
        }
    }
}
#define lson (rt<<1)
#define rson (rt<<1|1)
#define mid ((l+r)>>1)
struct Tree
{
    int l,r,lazy,v;
}tr[N<<2];
void pushup(int rt)
{
    tr[rt].v=tr[lson].v+tr[rson].v;
    tr[rt].v%=P;
}
void pushdown(int rt)
{
    int ll=tr[lson].l,lr=tr[lson].r;
    int rl=tr[rson].l,rr=tr[rson].r; 
    tr[lson].v+=(lr-ll+1)*tr[rt].lazy;
    tr[lson].v%=P;
    tr[lson].lazy+=tr[rt].lazy;
    tr[lson].lazy%=P;
    tr[rson].v+=(rr-rl+1)*tr[rt].lazy;
    tr[rson].v=P;
    tr[rson].lazy+=tr[rt].lazy;
    tr[rson].lazy%=P;
    tr[rt].lazy=0;
}
void build(int rt,int l,int r)
{
    tr[rt]={l,r,0,0};
    if(l==r)
    {
        tr[rt].v=a[l];
        tr[rt].v%=P;
        return;
    }
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(rt); 
}
void update(int rt,int sp,int ep,int k)
{
    int l=tr[rt].l,r=tr[rt].r;
    if(sp<=l&&r<=ep)
    {
        tr[rt].v+=(r-l+1)*k;
        tr[rt].v%=P;
        tr[rt].lazy+=k;
        tr[rt].lazy%=P;
        return ;
    }
    pushdown(rt);
    if(sp<=mid)
    {
        update(lson,sp,ep,k);
    }
    if(ep>mid)
    {
        update(rson,sp,ep,k);
    }
    pushup(rt);
}
int query(int rt,int sp,int ep)
{
    int l=tr[rt].l,r=tr[rt].r;
    if(sp<=l&&r<=ep)
    {
        return tr[rt].v;
    }
    pushdown(rt);
    if(ep<=mid)
    {
        return query(lson,sp,ep);
    }
    if(sp>mid)
    {
        return query(rson,sp,ep);
    }
    int L=query(lson,sp,ep);
    int R=query(rson,sp,ep);
    return (L+R)%P;
}
#undef lson
#undef rson
#undef mid 
void add_path(int x,int y,int k)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        update(1,dfn[x],dfn[top[x]],k);
        x=fa[x];    
    }
    if(dep[x]<dep[y])swap(x,y);
    update(1,dfn[y],dfn[x],k);
}

int sum_path(int x,int y)
{
    int res=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        res+=query(1,dfn[x],dfn[top[x]]);
        res%=P;
        x=fa[x];    
    }
    if(dep[x]<dep[y])swap(x,y);
    res+=query(1,dfn[y],dfn[x]);
    return res%P;
}
void add_subtree(int x,int k)
{
//  cout<<dfn[x]<<" "<<bot[x]<<endl;    
    update(1,dfn[x],bot[x],k);
}
int sum_subtree(int x)
{
    return query(1,dfn[x],bot[x])%P;
}
int main()
{
    cin>>n>>m>>root>>P;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x); 
     } 
     dep[root]=1;
     fa[root]=0;
     dfs1(root);
     cout<<1;
     dfs2(root,root); 
    build(1,1,n);
    while(m--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int x,y,z;
            cin>>x>>y>>z;
            add_path(x,y,z);
        }
        if(op==2)
        {
            int x,y;
            cin>>x>>y;
            cout<<sum_path(x,y)<<endl;
        }
        if(op==3)
        {
            int x,y;
            cin>>x>>y;
            add_subtree(x,y);
        }
        if(op==4)
        {
            int x;
            cin>>x;
            cout<<sum_subtree(x)<<endl;
        }
     } 
    return 0;
 }