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

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

---

• 两个 $dfs$ ，第一个用来预处理 $dep$ 和 $fa$ 和重儿子、轻儿子，第二个用来构造不超过 $logn$ 段序列，其中保证重链中的点编号连续。
• 用一种维护区间的数据结构，可以是 BIT 或者 Segment Tree 等，自用模板用 Segment Tree 。
• 时间复杂度最坏 $O(nlo{g}^{2}n)$ 。

---

模板：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define re register int
typedef pair<int,int>PII;
#define pb emplace_back
#define debug(a) cout<<a<<' ';
#define fer(i,a,b) for(re i=a;i<=b;i++)
#define der(i,a,b) for(re i=a;i>=b;i--)
int n,m,root,p;
const int N = 1e5+10,M = N<<1;
int w[N];
int e[M],ne[M],idx,h[N];
int dep[N];
int fa[N];
int son[N];
int sz[N];
int id[N];
int nw[N];//权值
int cnt;
int top[N];
struct Node{
    
    int l,r;
    int sum,lazy;
}tr[N<<2];
void add(int a,int b){
    
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs1(int u,int father,int depth){
    
    sz[u]=1;fa[u]=father;dep[u]=depth;
    for(int i=h[u];i!=-1;i=ne[i]){
    
        int j=e[i];
        if(j==father)continue;
        dfs1(j,u,depth+1);
        sz[u]+=sz[j];
        if(sz[son[u]]<sz[j])son[u]=j;
    }
}
void dfs2(int u,int t){
    //构造序列
    id[u]=++cnt;//序列中新编号
    nw[cnt]=w[u];
    top[u]=t;
    if(!son[u])return ;//叶子
    dfs2(son[u],t);
    for(int i=h[u];i!=-1;i=ne[i]){
    
        int j=e[i];
        if(j==fa[u]||j==son[u])continue;
        dfs2(j,j);
    }
}
void pushup(int u){
    
    tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u){
    
    auto &root=tr[u],&left=tr[u<<1],&right=tr[u<<1|1];
    if(root.lazy){
    
        left.lazy+=root.lazy;left.sum+=root.lazy*(left.r-left.l+1);left.sum%=p;
        right.lazy+=root.lazy;right.sum+=root.lazy*(right.r-right.l+1);right.sum%=p;
        root.lazy=0;
    }
}
void build(int u,int l,int r){
    
    if(l==r){
    
        tr[u]={
    l,r,nw[l]%p,0};
    }
    else{
    
        int mid=l+r>>1;
        tr[u]={
    l,r};
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}
void modify(int u,int l,int r,int k){
    
    if(l<=tr[u].l&&r>=tr[u].r){
    
        tr[u].lazy+=k;
        tr[u].sum+=k*(tr[u].r-tr[u].l+1);
        tr[u].sum%=p;
    }
    else{
    
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid)modify(u<<1,l,r,k);
        if(r>mid)modify(u<<1|1,l,r,k);
        pushup(u);
    }
}
int query(int u,int l,int r){
    
    if(l<=tr[u].l&&r>=tr[u].r){
    
        return tr[u].sum;
    }
    else{
    
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        int ans=0;
        if(l<=mid)ans+=query(u<<1,l,r);
        if(r>mid)ans+=query(u<<1|1,l,r);
        ans%=p;
        return ans;
    }
}
void modify_tree(int u,int k){
    
    modify(1,id[u],id[u]+sz[u]-1,k);
}
int query_tree(int u){
    
    return query(1,id[u],id[u]+sz[u]-1);
}
void modify_path(int u,int v,int k){
    
    while(top[u]!=top[v]){
    
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        modify(1,id[top[u]],id[u],k);
        u=fa[top[u]];
    }
    if(id[u]>id[v])swap(u,v);
    modify(1,id[u],id[v],k);
}   
int query_path(int u,int v){
    
    int res=0;
    while(top[u]!=top[v]){
    
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        res+=query(1,id[top[u]],id[u]);
        u=fa[top[u]];
    }
    if(id[u]>id[v])swap(u,v);
    res+=query(1,id[u],id[v]);
    res%=p;
    return res;
}
signed main(){
    
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m>>root>>p;
    memset(h,-1,sizeof h);
    fer(i,1,n)cin>>w[i];
    fer(i,1,n-1){
    
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    dfs1(root,-1,1);//预处理重轻、链
    dfs2(root,root);
    build(1,1,n);
    while(m--){
    
        int op,u,v,k;
        cin>>op>>u;
        if(op==1){
    
            cin>>v>>k;
            modify_path(u,v,k);
        }
        else if(op==2){
    
            cin>>v;
            cout<<query_path(u,v)<<endl;
        }
        else if(op==3){
    
            cin>>k;
            modify_tree(u,k);
        }
        else if(op==4){
    
            cout<<query_tree(u)<<endl;
        }
    }
    return 0;
}