更新日志

2025/01/07：开工。

概念

树链剖分，将树剖分成多个不相交的链。

视情况，我们选择合适的方式进行剖分。

我们往往可以借此解决“路径权值修改”问题，或者对启发式合并有所帮助。

方式

通常的，对于每个节点，我们视自己的需求，每次选择最优的一个子节点，加入其链，而其他子节点分别作为新链链头。

更详细的内容详见下方分类内部。

重链剖分

方式

对于每个儿子，我们选出子树最大的儿子，称为重儿子，并将其加入自己的链中。

同时，我们记录每个节点的 \(dfn\)，每次优先遍历重儿子。具体的作用将会在路径修改部分介绍。

剖分模板

int dcnt;
int fa[N],dep[N],siz[N],son[N];
int top[N],dfn[N],rnk[N];
void init(int now,int fid){
    fa[now]=fid;
    dep[now]=dep[fid]+1;
    siz[now]=1;
    son[now]=0;
    for(auto nxt:vs[now]){
        if(nxt==fid)continue;
        init(nxt,now);
        siz[now]+=siz[nxt];
        if(siz[nxt]>siz[son[now]])son[now]=nxt;
    }
}
void dfs(int now,int tp){
    top[now]=tp;
    dfn[now]=++dcnt;
    rnk[dcnt]=now;
    if(son[now])dfs(son[now],tp);
    for(auto nxt:vs[now]){
        if(nxt==fa[now]||nxt==son[now])continue;
        dfs(nxt,nxt);
    }
}

路径修改

这是树链剖分一个很常见的作用，借助重链剖分，我们大致可以做到 \(O(\log^2n)\) 单次修改。

我们将借助 \(dfs\) 序解决这个问题。

如果我们每次优先递归重儿子的话，不难发现，一条重链在 \(dfs\) 序上是连续的一段。

考虑如何快速处理路径修改问题，不难发现，一条路径，可以被拆分为多条重链。事实上，这是 \(\log n\) 级别的。因为一条路径上最多只会有 \(\log n\) 条轻链。这里不作具体证明。

我们同时操作路径的两端，如果二者在同一条重链上，直接区间修改即可；否则，就像倍增求 \(LCA\) 那样，我们将深度更深的点往上跳，跳到下一条重链上，并更新沿路的答案。直到二者相遇为止。

至于区间修改操作，利用线段树或树状数组即可。

相似的，我们可以写出路径权值查询。

路径修改/查询模板

void pathadd(int x,int y,int z){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        seg.add(dfn[top[x]],dfn[x],z);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    seg.add(dfn[x],dfn[y],z);
}

ll pathsum(int x,int y){
    ll res=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        res+=seg.query(dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    res+=seg.query(dfn[x],dfn[y]);
    return res;
}

子树修改

这其实与树链剖分无关，利用了 \(dfn\) 性质，子树内的节点也是连续的一段。

同样区间修改、查询即可。

例题

板子题

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define per(i,x,y) for(int i=x;i>=y;i--)

const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;

const int N=1e5+5;

int n,m,s;
ll mod;
ll a[N];
vec<int> vs[N];

int dcnt;
int fa[N],dep[N],siz[N],son[N];
int top[N],dfn[N],rnk[N];
void init(int now,int fid){
    fa[now]=fid;
    dep[now]=dep[fid]+1;
    siz[now]=1;
    son[now]=0;
    for(auto nxt:vs[now]){
        if(nxt==fid)continue;
        init(nxt,now);
        siz[now]+=siz[nxt];
        if(siz[nxt]>siz[son[now]])son[now]=nxt;
    }
}
void dfs(int now,int tp){
    top[now]=tp;
    dfn[now]=++dcnt;
    rnk[dcnt]=now;
    if(son[now])dfs(son[now],tp);
    for(auto nxt:vs[now]){
        if(nxt==fa[now]||nxt==son[now])continue;
        dfs(nxt,nxt);
    }
}

struct segment{
    ll dat[N*4],laz[N*4];
    void update(int x){
        dat[x]=(dat[x<<1]+dat[x<<1|1])%mod;
    }
    void pushdown(int x,int l,int r){
        int m=l+r>>1;
        (dat[x<<1]+=laz[x]*(m-l+1)%mod)%=mod;
        (dat[x<<1|1]+=laz[x]*(r-m)%mod)%=mod;
        (laz[x<<1]+=laz[x])%=mod;
        (laz[x<<1|1]+=laz[x])%=mod;
        laz[x]=0;
    }
    void build(int x=1,int l=1,int r=n){
        if(l==r){
            dat[x]=a[rnk[l]]%mod;
            return;
        }
        int m=l+r>>1;
        build(x<<1,l,m);
        build(x<<1|1,m+1,r);
        update(x);
    }
    void add(int lq,int rq,int v,int x=1,int l=1,int r=n){
        if(lq<=l&&r<=rq){
            (dat[x]+=v*(r-l+1)%mod)%mod;
            (laz[x]+=v)%=mod;
            return;
        }
        pushdown(x,l,r);
        int m=l+r>>1;
        if(lq<=m)add(lq,rq,v,x<<1,l,m);
        if(m<rq)add(lq,rq,v,x<<1|1,m+1,r);
        update(x);
    }
    ll query(int lq,int rq,int x=1,int l=1,int r=n){
        if(lq<=l&&r<=rq){
            return dat[x];
        }
        pushdown(x,l,r);
        int m=l+r>>1;
        ll res=0;
        if(lq<=m)(res+=query(lq,rq,x<<1,l,m))%=mod;
        if(m<rq)(res+=query(lq,rq,x<<1|1,m+1,r))%=mod;
        return res;
    }
}seg;

void pathadd(int x,int y,int z){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        seg.add(dfn[top[x]],dfn[x],z);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    seg.add(dfn[x],dfn[y],z);
}

ll pathsum(int x,int y){
    ll res=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        (res+=seg.query(dfn[top[x]],dfn[x]))%=mod;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    (res+=seg.query(dfn[x],dfn[y]))%=mod;
    return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>s>>mod;
    rep(i,1,n)cin>>a[i];
    rep(i,2,n){
        int u,v;cin>>u>>v;
        vs[u].pub(v);vs[v].pub(u);
    }
    init(s,s); 
    dfs(s,s);
    seg.build();
    int op,x,y,z;
    rep(i,1,m){
        cin>>op;
        if(op==1){
            cin>>x>>y>>z;
            pathadd(x,y,z);
        }
        if(op==2){
            cin>>x>>y;
            cout<<pathsum(x,y)<<"\n";
        }
        if(op==3){
            cin>>x>>z;
            seg.add(dfn[x],dfn[x]+siz[x]-1,z);
        }
        if(op==4){
            cin>>x;
            cout<<seg.query(dfn[x],dfn[x]+siz[x]-1)<<"\n";
        }
    }
    return 0;
}

应用

除了上述的路径修改之外，重链剖分还应用于树上启发式合并。

长链剖分

简介

与重链剖分相似，每次优先处理可以向下形成最长链的儿子。

应用

优化DP

如果某个DP的一个维度是深度，那么就可以使用长链剖分优化。

思路与重链剖分的树上启发式合并相似，优先跑长儿子，再暴力合并短儿子。

和重链剖分几乎没有差别，就不单独给模板了。