P3384 【模板】轻重链剖分/树链剖分

不要在意我的AC记录，那个是我用来调试的

#include<bits/stdc++.h>
using namespace std;
struct node{int to,next;};node bian[100010];
int n,m,r,p,q,w,ans,cnt,a[100010],head[100010],tree[100010*4],lazy[100010*4];
int fath[100010],dep[100010],size[100010],son[100010];
int top[100010],seg[100010],rev[100010];
void add(int x,int y){
    cnt++;
    bian[cnt].to=y;
    bian[cnt].next=head[x];
    head[x]=cnt;
}
void build(int k,int l,int r){
    if(l==r){
        tree[k]=a[rev[l]];
        return ;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    tree[k]=tree[k*2]+tree[k*2+1]; 
}
void addp(int k,int l,int r,int v){//修改辅助 
    lazy[k]+=v%p;
    tree[k]+=(r-l+1)*v%p;
}
void down(int k,int l,int r){
    int mid=(l+r)/2;
    addp(k*2,l,mid,lazy[k]);
    addp(k*2+1,mid+1,r,lazy[k]);
    lazy[k]=0; 
}
void change(int k,int l,int r,int x,int y,int z){
    if(l>y||r<x)return ;
    if(l>=x&&r<=y)return addp(k,l,r,z);
    if(lazy[k])down(k,l,r);
    int mid=(l+r)/2;
    change(k*2,l,mid,x,y,z);
    change(k*2+1,mid+1,r,x,y,z);
    tree[k]=((tree[k*2]%p)+(tree[k*2+1]%p))%p;
}
int query(int k,int l,int r,int x,int y){
    if(l>y||r<x)return 0;
    if(l>=x&&r<=y)return tree[k]%p;
    if(lazy[k])down(k,l,r);
    int mid=(l+r)/2;
    return (query(k*2,l,mid,x,y))%p+(query(k*2+1,mid+1,r,x,y))%p;
}
void dfs1(int r,int x){
    fath[x]=r;
    dep[x]=dep[r]+1;
    size[x]=1;
    for(int k=head[x];k;k=bian[k].next){
        if(bian[k].to!=r){
            dfs1(x,bian[k].to);
            size[x]+=size[bian[k].to];
            if(size[bian[k].to]>size[son[x]])son[x]=bian[k].to;
        } 
    }
}
void dfs2(int x){
    if(son[x]){
        top[son[x]]=top[x];
        seg[son[x]]=++seg[0];
        rev[seg[son[x]]]=son[x];
        dfs2(son[x]);
    }
    for(int k=head[x];k;k=bian[k].next){
        if(!top[bian[k].to]){
            top[bian[k].to]=bian[k].to;
            seg[bian[k].to]=++seg[0];
            rev[seg[bian[k].to]]=bian[k].to;
            dfs2(bian[k].to); 
        }
    }
}
void check(int x,int y){//树上两点之间修改查询 
    int tx=top[x],ty=top[y];
    while(tx!=ty){
        if(dep[tx]<dep[ty])swap(x,y),swap(tx,ty);
        if(q==1)change(1,1,seg[0],tx,x,w);//操作1修改
        if(q==2)ans+=query(1,1,seg[0],tx,x);//操作2查询 
        x=fath[tx],tx=top[x];
    }
    if(dep[x]>dep[y])swap(x,y);
    if(q==1)change(1,1,seg[0],seg[x],seg[y],w);//操作1修改
    if(q==2)ans+=query(1,1,seg[0],seg[x],seg[y]);//操作2查询 
}
int main(){
    cin>>n>>m>>r>>p;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n-1;i++){
        int x,y;cin>>x>>y;
        add(x,y);add(y,x);
    }
    dfs1(r,0);
    top[r]=r;seg[r]=++seg[0];rev[1]=r;
    dfs2(r); 
    build(1,1,seg[0]);  
    for(int i=1;i<=m;i++){
        int x,y;cin>>q;
        if(q==1){
            cin>>x>>y>>w;
            check(x,y);
        }
        if(q==2){
            cin>>x>>y;ans=0;
            check(x,y);
            cout<<ans%p<<endl;
        }
        if(q==3){
            cin>>x>>w;
            change(1,1,seg[0],seg[x],seg[x]+size[x]-1,w);
        }
        if(q==4){
            cin>>x;ans=0;
            query(1,1,seg[0],seg[x],seg[x]+size[x]-1);
            cout<<ans%p<<endl;
        }
    }
    return 0;
}