树链剖分 19分求调

代码里估计有一堆奇奇怪怪的 bug，调了几周调不出来

#include <iostream>
using namespace std;
#define maxn 100005
typedef long long ll;
int n,m,r,p,fa[maxn],deep[maxn],size[maxn],hson[maxn],top[maxn],dfn[maxn],rnk[maxn],d[maxn],tot,cnt;
ll a[maxn],num[maxn*2-1],lazy[maxn*2-1];
struct edge{
    int to,next;
}e[maxn*2];
void addedge(int u,int v){
    e[++tot].to=v;
    e[tot].next=d[u];
    d[u]=tot;
}
void dfs1(int x){
    size[x]=1;
    for(int i=d[x];i;i=e[i].next){
        if(e[i].to!=fa[x]){
            fa[e[i].to]=x;
            deep[e[i].to]=deep[x]+1;
            dfs1(e[i].to);
            size[x]+=size[e[i].to];
            if(!hson[x]||size[e[i].to]>size[hson[x]]){
                hson[x]=e[i].to;
            }
        }
    }
}
void dfs2(int x,int t){
    top[x]=t;
    dfn[x]=++cnt;
    rnk[cnt]=x;
    if(!hson[x]){
        return;
    }
    dfs2(hson[x],t);
    for(int i=d[x];i;i=e[i].next){
        if(e[i].to!=hson[x]&&e[i].to!=fa[x]){
            dfs2(e[i].to,e[i].to);
        }
    }
}
void build(int l,int r,int root){
    if(l==r){
        num[root]=a[rnk[l]];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,root*2);
    build(mid+1,r,root*2+1);
    num[root]=num[root*2]+num[root*2+1];
}
void pushdown(int l,int r,int root){
    int mid=(l+r)/2;
    num[root*2]+=(mid-l+1)*lazy[root];
    lazy[root*2]+=lazy[root];
    num[root*2+1]+=(r-mid)*lazy[root];
    lazy[root*2+1]+=lazy[root];
    lazy[root]=0;
}
void add(int x,int y,int k,int l,int r,int root){
    if(l>=x&&r<=y){
        num[root]+=(r-l+1)*k;
        lazy[root]+=k;
        return;
    }
    if(lazy[root]&&l!=r){
        pushdown(l,r,root);
    }
    int mid=(l+r)/2;
    if(mid>=x){
        add(x,y,k,l,mid,root*2);
    }
    if(mid<y){
        add(x,y,k,mid+1,r,root*2+1);
    }
    num[root]=num[root*2]+num[root*2+1];
}
ll get(int x,int y,int l,int r,int root){
    if(l>=x&&r<=y){
        return num[root];
    }
    if(lazy[root]&&l!=r){
        pushdown(l,r,root);
    }
    int mid=(l+r)/2;
    ll sum=0;
    if(mid>=x){
        sum+=get(x,y,l,mid,root*2);
    }
    if(mid<y){
        sum+=get(x,y,mid+1,r,root*2+1);
    }
    return sum;
}
int main(){
    cin>>n>>m>>r>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        addedge(u,v);
        addedge(v,u);
    }
    dfs1(r);
    dfs2(r,r);
    build(1,n,1);
    for(int i=1;i<=m;i++){
        int op;
        cin>>op;
        switch(op){
            case 1:{
                int x,y;
                ll z;
                cin>>x>>y>>z;
                while(top[x]!=top[y]){
                    if(deep[top[x]]<deep[top[y]]){
                        swap(x,y);
                    }
                    add(dfn[top[x]],dfn[x],z,1,n,1);
                    x=fa[top[x]];
                }
                if(deep[top[x]]<deep[top[y]]){
                    swap(x,y);
                }
                add(dfn[y],dfn[x],z,1,n,1);
                break;
            }
            case 2:{
                int x,y;
                ll ans=0;
                cin>>x>>y;
                while(top[x]!=top[y]){
                    if(deep[top[x]]<deep[top[y]]){
                        swap(x,y);
                    }
                    ans+=get(dfn[top[x]],dfn[x],1,n,1);
                    x=fa[top[x]];
                }
                if(deep[top[x]]<deep[top[y]]){
                    swap(x,y);
                }
                ans+=get(dfn[y],dfn[x],1,n,1);
                cout<<ans%p<<endl;
                break;
            }
            case 3:{
                int x;
                ll z;
                cin>>x>>z;
                add(dfn[x],dfn[x]+size[x]-1,z,1,n,1);
                break;
            }
            case 4:{
                int x;
                cin>>x;
                cout<<get(dfn[x],dfn[x]+size[x]-1,1,n,1)%p<<endl;
            }
        }
    }
    return 0;
}