模版-树链剖分

#include<bits/stdc++.h>
using namespace std;
#define maxn 500000+10
#define LL long long
LL no[maxn];      /// 所属链的编号
LL top[maxn];     /// top节点
LL dee[maxn];     /// 深度（然而我并没有用到）
LL fa[maxn];      /// 父亲节点
LL zs[maxn];      /// 重儿子
LL sz[maxn];      /// 子节点个数
LL dfn[maxn];     /// dfs的编号
LL tre[maxn];     /// 建树
LL a[maxn],b[maxn]; /// 储存节点的value
bool vis[maxn];    /// 第一遍 dfs 的标记数组
long long lz[maxn];///  懒惰数组
vector<long long>q[maxn]; /// 记录节点信息
long long n,m,r,P;
long long tot=0,z=1; /// dfs的编号 和链的编号

void dfs(long long u,long long y){   ///第一遍dfs记录 节点的深度，重儿子，节点个数
   sz[u]=1;
   dee[u]=y;
   long long mx=-1;
   for(long long j=0;j<q[u].size();j++){
      long long v=q[u][j];
      if(!vis[v]){
         vis[v]=1;
         fa[v]=u;
         dfs(v,y+1);
         sz[u]+=sz[v];
         if(sz[v]>mx){
            mx=sz[v];
            zs[u]=v;
         }
      }
   }
}

void dfs2(long long u,long long y){ ///第二遍dfs 记录 每条链的编号以及每个节点的编号
     dfn[u]=++tot;
     b[tot]=a[u];
     top[u]=y;
     no[u]=z;
     if(zs[u]==0) return ;
     if(zs[u]){
       dfs2(zs[u],y);
     }
     for(long long j=0;j<q[u].size();j++){
         long long v=q[u][j];
         if(v!=zs[u]&&v!=fa[u]){
           z++;
           dfs2(v,v);
         }
     }
}

void lazy(long long in,long long rt){
    if(lz[in]){
       lz[in*2]+=lz[in];
       lz[in*2+1]+=lz[in];
       tre[in*2]+=lz[in]*(rt-rt/2);
       tre[in*2+1]+=lz[in]*(rt/2);
       lz[in]=0;
    }
}
void build(long long l,long long r,long long in){
   if(l==r){
      tre[in]=b[l];
      return ;
   }
   long long mid=(l+r)/2;
   build(l,mid,in*2);
   build(mid+1,r,in*2+1);
   tre[in]=tre[in*2]+tre[in*2+1];
}
long long query(long long l,long long r,long long x,long long y,long long in){
   if(l==x&&r==y){
      return tre[in]%P;
   }
   lazy(in,y-x+1);
   long long mid=(x+y)/2;
   if(r<=mid){
      return query(l,r,x,mid,in*2)%P;
   }else if(l>mid){
      return query(l,r,mid+1,y,in*2+1)%P;
   }
   return (query(l,mid,x,mid,in*2)%P+query(mid+1,r,mid+1,y,in*2+1)%P)%P;
}
void updata(long long l,long long r,long long x,long long y,long long in,long long c){
   if(l==x&&r==y){
       tre[in]+=c*(y-x+1);
       lz[in]+=c;
       return ;
   }
   lazy(in,y-x+1);
   long long mid=(x+y)/2;
   if(r<=mid){
      updata(l,r,x,mid,in*2,c);
   }else if(l>mid){
      updata(l,r,mid+1,y,in*2+1,c);
   }
   else{
      updata(l,mid,x,mid,in*2,c);
      updata(mid+1,r,mid+1,y,in*2+1,c);
   }
  tre[in]=tre[in*2]+tre[in*2+1];
}
/// 以上正常的线段树操作

void xiugai1(long long x,long long y,long long z){
   long long xx=no[x],yy=no[y];                /// 属于那条链
   if(xx==yy){                                 /// 判断链的编号大小然后做出修改
      long long xxx=dfn[x],yyy=dfn[y];         /// 相同 属于同一条链 同一条链的编号是连续的
      if(xxx>yyy) swap(xxx,yyy);
      updata(xxx,yyy,1,n,1,z);
      return ;
   }
   if(xx>yy){                                 /// x>y 修改x所在链的区间 
      updata(dfn[top[x]],dfn[x],1,n,1,z);
      xiugai1(fa[top[x]],y,z);                /// 递归寻找其top节点的父亲节点的链和y比较
   }
   if(xx<yy){
      updata(dfn[top[y]],dfn[y],1,n,1,z);
      xiugai1(x,fa[top[y]],z);
   }
}

long long chaxun1(long long x,long long y){   /// 和修改操作基本一致

   long long xx=no[x],yy=no[y];
   if(xx==yy){
      long long xxx=dfn[x],yyy=dfn[y];
      if(xxx>yyy) swap(xxx,yyy);
      return query(xxx,yyy,1,n,1)%P;
   }
   long long ans=0;
   if(xx>yy){
      ans+=query(dfn[top[x]],dfn[x],1,n,1)%P;
      ans%=P;
      ans+=chaxun1(fa[top[x]],y)%P;
      ans%=P;
   }
   if(xx<yy){
      ans+=query(dfn[top[y]],dfn[y],1,n,1)%P;
      ans%=P;
      ans+=chaxun1(x,fa[top[y]])%P;
      ans%=P;
   }
   return ans%P;
} 

long long chaxun(long long x){                /// 某一节点的子树的编号一定连续 只要找到 这个节点的sz个数和 dfn 编号即可
   return query(dfn[x],dfn[x]+sz[x]-1,1,n,1)%P;
}

void xiugai(long long x,long long y){         /// 同上
   updata(dfn[x],dfn[x]+sz[x]-1,1,n,1,y);
}

/// 以下就是常规的操作
int main(){
    cin>>n>>m>>r>>P;
    memset(lz,0,sizeof(lz));
    for(long long j=1;j<=n;j++){
       cin>>a[j];
    }
    memset(vis,0,sizeof(vis));
    for(long long j=1;j<n;j++){
       long long x,y;
       cin>>x>>y;
       q[x].push_back(y);
       q[y].push_back(x);
    }
    vis[r]=1;
    dfs(r,1LL*1);

    memset(vis,0,sizeof(vis));
    dfs2(r,r);
    build(1,n,1);

    for(long long j=0;j<m;j++){
        long long nu,x,y,z;
        cin>>nu;
        if(nu==1){
           cin>>x>>y>>z;
           xiugai1(x,y,z);
        }
        if(nu==2){
           cin>>x>>y;
           cout<<chaxun1(x,y)%P<<endl;;
        }
        if(nu==3){
          cin>>x>>y;
          xiugai(x,y);
        }
        if(nu==4){
           cin>>x;
           cout<<chaxun(x)%P<<endl;
        }
    }

    return 0；
}