树链剖分|树上启发式合并

DEV3937 / 2024-10-11 / 原文

树链剖分

分为重链剖分和长链剖分以及其他奇怪的剖分。以重剖为主。

重链剖分

将树上问题重链剖分为序列问题（经常是 DFS 序）然后用数据结构（经常是线段树）维护。

剖分部分

定义：

重儿子：对于一个点，其儿子中，子树最大的那个；
重边：父亲到重儿子的连边；
轻儿子：除了重儿子以外的儿子；
轻边：父亲到轻儿子的连边。

证明一个东西：一条链上（不是路径，虽然差不多，路径就是两条链拼起来）至多有 $\log n$ 条轻边。

很显然，每次若是走轻边，子树大小都至少会减少一半，所以至多走 $\log n$ 次就到底了。

于是我们即使暴力维护轻边的复杂度都是 $O(F(n)\log n)$ 的，$F(n)$ 是数据结构单点操作复杂度。

而由于重边在儿子中的唯一性，所以所有的重边形成了若干条链，不妨称之重链。

一条链上包含多条重链。由于轻重边的交替排布，重链的数量级也是 $\log n$ 的。考虑到大部分数据结构维护的是下标连续的区间，于是这里有一个小 trick，DFS 求 dfn 时，优先走重边，这样重链上的下标就连续了，所以我们只要做一次数据结构的区间操作即可维护重边上的信息，记 $top(u)$ 为包含 $u$ 的重链的链头，则每次跳 $u\to fa(top(u))$ 即可一次跳过一条重链加一条轻边，时间复杂度 $O(F'(n)\log n)$，$F'(n)$ 为数据结构区间操作复杂度，对于线段树这种的，$F'(n)\doteq F(n)$。

综上对于一条链的操作，复杂度就为 $O(F(n)\log n)$。

例题：

给你一棵带边权树，支持下列操作：

查询子树和

查询 $u,v$ 路径和

修改子树边权

修改路径边权

先 DFS 出 dfn，然后操作 1、3 对应了一段连续的区间，直接线段树区间操作即可；操作 2、4 首先将路径拆成两条链 $(u,\text{lca}),(\text{lca},v)$，然后分别剖即可。时间复杂度分别为 $O(\log n),O(\log^2 n)$。

实现

第一遍 DFS 求出以下信息：

$dep(u)$：$u$ 的深度；
$siz(u)$：$u$ 子树大小；
$son(u)$：$u$ 的重儿子；
$fa(u)$：$u$ 的父亲。

void dfs1(int u,int Fa){
    dep[u]=dep[Fa]+1;
    fa[u]=Fa;
    int mxson,mxsiz=0;
    for(edge v:e[u]){
        if(v.v!=fa){
            dfs1(v.v,u);
            siz[u]+=siz[v.v];
            if(siz[v.v]>mxsiz)
                mxsiz=siz[v.v],mzson=v.v;
        }
    }
    son[u]=mxson;
}

第二遍 DFS 求出以下信息：

$top(u)$：包含 $u$ 的重链链头；
$dfn(u)$：$u$ 的 dfn；
$idx(u)$：$u$ 的 dfn 逆向索引。

void dfs2(int u,int t){
    top[u]=t;
    dfn[u]=++dfncnt;
    idx[dfncnt]=u;
    if(top[son[u]]!=t) dfs2(son[u],son[u]);
    else dfs2(son[u],t);
    for(edge v:e[u]){
        if(v.v!=fa[u]&&v.v!=son[u]){
            dfs2(v.v,v.v); // 轻儿子肯定不在 u 的重链上
        }
    }
}

修改路径：

void modify_chain(int u,int v,int x){
    int fu=u,fv=v;
    while(top[fu]!=top[fv]){
        if(dep[top[fu]]<dep[top[fv]]) swap(fu,fv); 
        modify(1,1,n,dfn[top[fu]],dfn[fu],x);
        fu=fa[top[fu]]; // 每次选深的跳直到到同一重链上
    }
    if(dep[fu]>dep[fv]) swap(fu,fv);
    modify(1,1,dfn[fu],dfn[fv],x);
}

查询路径：

int query_chain(int u,int v,int x){
    int fu=u,fv=v,res=0;
    while(top[fu]!=top[fv]){
        if(dep[top[fu]]<dep[top[fv]]) swap(fu,fv); 
        res+=query(1,1,n,dfn[top[fu]],dfn[fu],x);
        fu=fa[top[fu]]; // 每次选深的跳直到到同一重链上
    }
    if(dep[fu]>dep[fv]) swap(fu,fv);
    res+=query(1,1,dfn[fu],dfn[fv],x);
    return res;
}

特殊的，如果信息在点上，则可以把信息转移到边 $(u,fa(u))$ 上。