树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。

具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。

树链剖分（树剖/链剖）有多种形式，如重链剖分，长链剖分和用于 Link/cut Tree 的剖分（有时被称作“实链剖分”），大多数情况下（没有特别说明时），“树链剖分”都指“重链剖分”。

重链剖分可以将树上的任意一条路径划分成不超过 $O(\log n)$ 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。

重链剖分还能保证划分出的每条链上的结点 DFS 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。

如：

1. 修改树上两点之间的路径上所有点的值。
2. 查询树上两点之间的路径上结点权值的和/极值/其它（在序列上可以用数据结构维护，便于合并的信息）。

除了配合数据结构来维护树上路径信息，树剖还可以用来 $O(\log n)$ （且常数较小）地求 LCA。在某些题目中，还可以利用其性质来灵活地运用树剖。

我们给出一些定义：

定义重子结点表示其子结点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子结点，就无重子结点。

定义轻子结点表示剩余的所有子结点。

从这个结点到重子结点的边为重边。

到其他轻子结点的边为轻边。

若干条首尾衔接的重边构成重链。

把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。

如图：

树剖的实现分两个 DFS 的过程。伪代码如下：

第一个 DFS 记录每个结点的父节点（father）、深度（deep）、子树大小（size）、重子结点（hson）。 $$ \begin{array}{l}\text{TREE-BUILD}(u,dep)\\ \begin{array}{ll} 1 & u.hson\gets 0\\ 2&u.hson.size\gets 0\\ 3 & u.deep\gets dep\\ 4&u.size\gets 1\\ 5 & \textbf{for}\ \text{each}\ u\text{'s son}\ v\\ 6 & \qquad u.size\gets u.size+\text{TREE-BUILD}(v,dep+1)\\ 7 & \qquad v.father\gets u\\ 8 & \qquad \textbf{if}\ v.size>u.hson.size\\ 9 & \qquad\qquad u.hson\gets v\\ 10 & \textbf{return}\ u.size \end{array}\end{array} $$ 第二个 DFS 记录所在链的链顶（top，应初始化为结点本身）、重边优先遍历时的 DFS 序（dfn）、DFS 序对应的结点编号（rank）。 $$ \begin{array}{l}\text{TREE-DECOMPOSITION }(u,top)\\ \begin{array}{ll} 1 & u.top\gets top\\ 2 & tot\gets tot+1\\ 3 & u.dfn\gets tot\\ 4 & rank(tot)\gets u\\ 5 & \textbf{if}\ u.hson\ \text{is not}\ 0\\ 6 & \qquad\text{TREE-DECOMPOSITION}(u.hson,top)\\ 7 & \qquad\textbf{for }\text{each }u\text{'s son }v\\ 8& \qquad\qquad\textbf{if }v\text{ is not }u.hson\\ 9 & \qquad\qquad\text{TREE-DECOMPOSITION }(v,v) \end{array}\end{array} $$ 以下为代码实现。

我们先给出一些定义：

• $fa(x)$ 表示结点 $x$ 在树上的父亲。
• $dep(x)$ 表示结点 $x$ 在树上的深度。
• $siz(x)$ 表示结点 $x$ 的子树的结点个数。
• $son(x)$ 表示结点 $x$ 的重儿子。
• $top(x)$ 表示结点 $x$ 所在重链的顶部结点（深度最小）。
• $dfn(x)$ 表示结点 $x$ 的DFS序，也是其在线段树中的编号。
• $rnk(x)$ 表示 DFS 序所对应的结点编号，有 $rnk(dfn(x))=x$ 。

我们进行两遍 DFS 预处理出这些值，其中第一次 DFS 求出 $fa(x),dep(x),siz(x),son(x)$，第二次 DFS 求出 $top(x),dfn(x),rnk(x)$。

void dfs1(int o){
    son[o]=-1;
    siz[o]=1;
    for(int j=h[o];j;j=nxt[j]){
        if(!dep[p[j]]){
            dep[p[j]]=dep[o]+1;
            fa[p[j]]=o;
            dfs1(p[j]);
            siz[o]+=siz[p[j]];
            if(son[o]==-1||siz[p[j]]>siz[son[o]]) son[o]=p[j];
        }
    }
}
void dfs2(int o,int t){
    top[o]=t;
    cnt++;
    dfn[o]=cnt;
    rnk[cnt]=o;
    if(son[o]==-1) return;
    dfs2(son[o],t);// 优先对重儿子进行 DFS ，可以保证同一条重链上的点 DFS 序连续
    for(int j=h[o];j;j=nxt[j]){
        if(p[j]!=son[o]&&p[j]!=fa[o]) dfs2(p[j],p[j]);
    }
}

树上每个结点都属于且仅属于一条重链。

重链开头的结点不一定是重子结点（因为重边是对于每一个结点都有定义的）。

所有的重链将整棵树完全剖分。

在剖分时优先遍历重儿子，最后重链的 DFS 序就会是连续的。

在剖分时重边优先遍历，最后树的 DFN 序上，重链内的 DFN 序是连续的。按 DFN 排序后的序列即为剖分后的链。

一棵子树内的 DFN 序是连续的。

可以发现，当我们向下经过一条轻边时，所在子树的大小至少会除以二。

因此，对于树上的任意一条路径，把它拆分成从 LCA 分别向两边往下走，分别最多走 $O(\log n)$次，因此，树上的每条路径都可以被拆分成不超过 $O(\log n)$条重链。

用树链剖分求树上两点路径权值和，伪代码如下： $$ \begin{array}{l}\text{TREE-PATH-SUM }(u,v)\\ \begin{array}{ll} 1 & tot\gets 0 \\ 2 & \textbf{while }u.top\text{ is not }v.top\\ 3 & \qquad\textbf{if }u.top.deep<v.top.deep\\ 4& \qquad\qquad\text{SWAP}(u,v)\\ 5 & \qquad tot\gets tot+\text{sum of values between }u\text{ and }u.top\\ 6 & \qquad u \gets u.top.father\\ 7 & tot\gets tot +\text{sum of values between }u\text{ and }v\\ 8 & \textbf{return }tot \end{array}\end{array} $$ 链上的 DFS 序是连续的，可以使用线段树、树状数组维护。

每次选择深度较大的链往上跳，直到两点在同一条链上。

同样的跳链结构适用于维护、统计路径上的其他信息。

有时会要求维护子树上的信息，譬如将以 $x$ 为根的子树的所有结点的权值增加 $v$。

在 DFS 搜索的时候，子树中的结点的 DFS 序是连续的。

每一个结点记录 bottom 表示所在子树连续区间末端的结点。

这样就把子树信息转化为连续的一段区间信息。

不断向上跳重链，当跳到同一条重链上时，深度较小的结点即为 LCA。

向上跳重链时需要先跳所在重链顶端深度较大的那个。

参考代码：

int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]>dep[top[v]])
            u=fa[top[u]];
        else
            v=fa[top[v]];
    }
    return dep[u]>dep[v]?v:u;
}

P3384 【模板】轻重链剖分

OI Wiki