树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。
具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。
树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作“实链剖分”），大多数情况下（没有特别说明时），“树链剖分”都指“重链剖分”。
重链剖分可以将树上的任意一条路径划分成不超过
重链剖分还能保证划分出的每条链上的节点 DFS 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。
如：
- 修改 树上两点之间的路径上 所有点的值。
- 查询 树上两点之间的路径上 节点权值的 和/极值/其它（在序列上可以用数据结构维护，便于合并的信息）。
除了配合数据结构来维护树上路径信息，树剖还可以用来
我们给出一些定义：
定义 重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。
定义 轻子节点 表示剩余的所有子结点。
从这个结点到重子节点的边为 重边。
到其他轻子节点的边为 轻边。
若干条首尾衔接的重边构成 重链。
把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。
如图：
树剖的实现分两个 DFS 的过程。伪代码如下：
第一个 DFS 记录每个结点的父节点（father）、深度（deep）、子树大小（size）、重子节点（hson）。
第二个 DFS 记录所在链的链顶（top，应初始化为结点本身）、重边优先遍历时的 DFS 序（dfn）、DFS 序对应的节点编号（rank）。
以下为代码实现。
我们先给出一些定义：
-
$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 求出
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]);
}树上每个节点都属于且仅属于一条重链。
重链开头的结点不一定是重子节点（因为重边是对于每一个结点都有定义的）。
所有的重链将整棵树 完全剖分。
在剖分时 重边优先遍历，最后树的 DFN 序上，重链内的 DFN 序是连续的。按 DFN 排序后的序列即为剖分后的链。
一颗子树内的 DFN 序是连续的。
可以发现，当我们向下经过一条 轻边 时，所在子树的大小至少会除以二。
因此，对于树上的任意一条路径，把它拆分成从
用树链剖分求树上两点路径权值和，伪代码如下：
链上的 DFS 序是连续的，可以使用线段树、树状数组维护。
每次选择深度较大的链往上跳，直到两点在同一条链上。
同样的跳链结构适用于维护、统计路径上的其他信息。
有时会要求，维护子树上的信息，譬如将以
在 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;
}[!NOTE] 怎么有理有据地卡树剖
一般情况下树剖的
$O(\log n)$ 常数不满很难卡，如果要卡只能建立二叉树深度低。于是我们可以考虑折中方案。
我们建立一颗
$\sqrt{n}$ 个节点的二叉树。对于每个节点到其儿子的边，我们将其替换成一条长度为$\sqrt{n}$ 的链。这样子我们可以将随机询问轻重链切换次数卡到平均
$\frac{\log n}{2}$ 次，同时有$O(\sqrt{n} \log n)$ 的深度。加上若干随机叶子看上去可以卡树剖。但是树剖常数小有可能卡不掉。
对一棵有
- 修改单个节点的权值；
- 查询
$u$ 到$v$ 的路径上的最大权值； - 查询
$u$ 到$v$ 的路径上的权值之和。
保证
根据题面以及以上的性质，你的线段树需要维护三种操作：
- 单点修改；
- 区间查询最大值；
- 区间查询和。
单点修改很容易实现。
由于子树的 DFS 序连续（无论是否树剖都是如此），修改一个节点的子树只用修改这一段连续的 DFS 序区间。
问题是如何修改/查询两个节点之间的路径。
考虑我们是如何用 倍增法求解 LCA 的。首先我们 将两个节点提到同一高度，然后将两个节点一起向上跳。对于树链剖分也可以使用这样的思想。
在向上跳的过程中，如果当前节点在重链上，向上跳到重链顶端，如果当前节点不在重链上，向上跳一个节点。如此直到两节点相同。沿途更新/查询区间信息。
对于每个询问，最多经过
给出一种代码实现：
// st 是线段树结构体
int querymax(int x, int y) {
int ret = -inf, fx = top[x], fy = top[y];
while (fx != fy) {
if (dep[fx] >= dep[fy])
ret = max(ret, st.query1(1, 1, n, dfn[fx], dfn[x])), x = fa[fx];
else
ret = max(ret, st.query1(1, 1, n, dfn[fy], dfn[y])), y = fa[fy];
fx = top[x];
fy = top[y];
}
if (dfn[x] < dfn[y])
ret = max(ret, st.query1(1, 1, n, dfn[x], dfn[y]));
else
ret = max(ret, st.query1(1, 1, n, dfn[y], dfn[x]));
return ret;
}这是一道交互题，也是树剖的非传统应用。
有一棵以
节点数不超过
首先可以通过
然后考虑按深度从小到大确定每个节点的父亲，这样的话确定一个节点的父亲时其所有祖先一定都是已知的。
确定一个节点的父亲之前，先对树已知的部分进行重链剖分。
假设我们需要在子树
其中红色虚线是一条重链，$d$ 是询问的结果即
这样的话，如果
时间复杂度
具体地，设
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 3010;
int n, fa[N], ch[N][2], dep[N], siz[N], son[N], bot[N], id[N];
int query(int u, int v) {
printf("? %d %d\n", u, v);
fflush(stdout);
int d;
scanf("%d", &d);
return d;
}
void setFather(int u, int v) {
fa[v] = u;
if (ch[u][0])
ch[u][1] = v;
else
ch[u][0] = v;
}
void dfs(int u) {
if (ch[u][0]) dfs(ch[u][0]);
if (ch[u][1]) dfs(ch[u][1]);
siz[u] = siz[ch[u][0]] + siz[ch[u][1]] + 1;
if (ch[u][1])
son[u] = int(siz[ch[u][0]] < siz[ch[u][1]]);
else
son[u] = 0;
if (ch[u][son[u]])
bot[u] = bot[ch[u][son[u]]];
else
bot[u] = u;
}
void solve(int u, int k) {
if (!ch[u][0]) {
setFather(u, k);
return;
}
int d = query(k, bot[u]);
int v = bot[u];
while (dep[v] > (dep[k] + dep[bot[u]] - d) / 2) v = fa[v];
int w = ch[v][son[v] ^ 1];
if (w)
solve(w, k);
else
setFather(v, k);
}
int main() {
int i;
scanf("%d", &n);
for (i = 2; i <= n; ++i) {
id[i] = i;
dep[i] = query(1, i);
}
sort(id + 2, id + n + 1, [](int x, int y) { return dep[x] < dep[y]; });
for (i = 2; i <= n; ++i) {
dfs(1);
solve(1, id[i]);
}
printf("!");
for (i = 2; i <= n; ++i) printf(" %d", fa[i]);
printf("\n");
fflush(stdout);
return 0;
}长链剖分本质上就是另外一种链剖分方式。
定义 重子节点 表示其子节点中子树深度最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。
定义 轻子节点 表示剩余的子结点。
从这个结点到重子节点的边为 重边。
到其他轻子节点的边为 轻边。
若干条首尾衔接的重边构成 重链。
把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。
如图（这种剖分方式既可以看成重链剖分也可以看成长链剖分）：
长链剖分实现方式和重链剖分类似，这里就不再展开。
首先，我们发现长链剖分从一个节点到根的路径的轻边切换条数是
[!NOTE] 如何构造数据将轻重边切换次数卡满
我们可以构造这么一颗二叉树 T：
假设构造的二叉树参数为
$D$ 。若
$D \neq 0$ , 则在左儿子构造一颗参数为$D-1$ 的二叉树，在右儿子构造一个长度为$2D-1$ 的链。若
$D = 0$ , 则我们可以直接构造一个单独叶节点，并且结束调用。这样子构造一定可以将单独叶节点到根的路径全部为轻边且需要
$D^2$ 级别的节点数。取
$D=\sqrt{n}$ 即可。
一般情况下可以使用长链剖分来优化的 DP 会有一维状态为深度维。
我们可以考虑使用长链剖分优化树上 DP。
具体的，我们每个节点的状态直接继承其重儿子的节点状态，同时将轻儿子的 DP 状态暴力合并。
[!NOTE] CF 1009F
我们设
$f_{i,j}$ 表示在子树 i 内，和 i 距离为 j 的点数。直接暴力转移时间复杂度为
$O(n^2)$ 我们考虑每次转移我们直接继承重儿子的 DP 数组和答案，并且考虑在此基础上进行更新。
首先我们需要将重儿子的 DP 数组前面插入一个元素 1, 这代表着当前节点。
然后我们将所有轻儿子的 DP 数组暴力和当前节点的 DP 数组合并。
注意到因为轻儿子的 DP 数组长度为轻儿子所在重链长度，而所有重链长度和为
$n$ 。也就是说，我们直接暴力合并轻儿子的总时间复杂度为
$O(n)$ 。
注意，一般情况下 DP 数组的内存分配为一条重链整体分配内存，链上不同的节点有不同的首位置指针。
DP 数组的长度我们可以根据子树最深节点算出。
例题参考代码：
当然长链剖分优化 DP 技巧非常多，包括但是不仅限于打标记等等。这里不再展开。
参考 租酥雨的博客。
即询问一个点向父亲跳
首先我们假设我们已经预处理了每一个节点的
现在我们假设我们找到了询问节点的
我们考虑求出其所在重链的节点并且按照深度列入表格。假设重链长度为
同时我们在预处理的时候找到每条重链的根节点的
根据长链剖分的性质，$k-2^i < 2^i \leq d$, 也就是说，我们可以
预处理需要倍增出
预处理复杂度
「luogu P3379」【模板】最近公共祖先（LCA）（树剖求 LCA 无需数据结构，可以用作练习）
「JLOI2014」松鼠的新家（当然也可以用树上差分）
「POI2014」Hotel 加强版（长链剖分优化 DP)
攻略（长链剖分优化贪心）