树链剖分的核心作用是将静态树分解为若干条重链，使线段树能高效支持路径查询与修改操作。它要求树结构固定，适用于路径最大值、路径和等操作，时间复杂度为O(log²n)，不适用于动态树或非路径问题。
树链剖分的核心作用是什么
树链剖分不是银弹，它只解决一类特定问题：在静态树上快速支持路径修改和路径查询（比如路径最大值、路径和、路径赋值等），且要求操作复杂度不能退化到 O(n)。它本身不处理动态加边删边、LCA 以外的拓扑变化，也不替代线段树——它只是把树“拉直”成若干条链，让线段树能管得住。
关键判断：如果你的问题满足「树结构固定 + 需要频繁查/改 u→v 路径上的信息」，且单次操作期望 O(log²n)，那树链剖分值得上；否则别硬套，可能写个倍增 LCA + 暴力跳父亲更清晰。
剖分前必须搞定的两个数组：dep、sz、fa、son
这四个数组是后续所有逻辑的基础，必须一次算准，否则整个剖分失效。
-
dep[u]：节点 u 的深度（根为 0 或 1 都行，但要统一） -
sz[u]：以 u 为根的子树大小 -
fa[u]：u 的父节点 -
son[u]：u 的重儿子（子树大小最大的那个儿子，若多个取其一即可）
常见错误：
立即学习“C++免费学习笔记（深入）”；
- DFS 顺序错乱：先算
sz和son必须用后序遍历（递归完所有子树再更新），否则sz[u]不准 - 忘记初始化
son[u] = 0或-1，导致未更新节点参与后续链划分 - 根节点的
fa[root]没设为 0 或 -1，上线段树时越界
示例片段（DFS1）：
void dfs1(int u, int f) {
fa[u] = f;
dep[u] = dep[f] + 1;
sz[u] = 1;
son[u] = 0;
for (int v : g[u]) {
if (v == f) continue;
dfs1(v, u);
sz[u] += sz[v];
if (!son[u] || sz[v] > sz[son[u]]) son[u] = v;
}
}
如何正确构建重链与线段树映射：top、id、rk
这一步决定你能不能把路径拆成 O(log n) 条链。核心是第二次 DFS（DFS2），按“先走重儿子”原则分配时间戳。
必须维护三个数组：
-
top[u]：u 所在重链的顶部节点（链头） -
id[u]：u 在线段树中的下标（即欧拉序位置） -
rk[id]：下标 id 对应的原节点编号（反查用）
容易踩的坑：
- DFS2 中对轻儿子调用时没重置
top[v] = v，导致整条轻子树挂在错误链头下 -
id从 1 开始计数，但线段树建树用了 0-based，导致区间错位 - 忘记在 DFS2 入口处执行
id[u] = ++cnt; rk[cnt] = u;，导致线段树索引全空
典型 DFS2 片段：
int cnt = 0;
void dfs2(int u, int t) {
top[u] = t;
id[u] = ++cnt;
rk[cnt] = u;
if (son[u]) dfs2(son[u], t); // 重儿子继承链头
for (int v : g[u]) {
if (v == fa[u] || v == son[u]) continue;
dfs2(v, v); // 轻儿子自成新链
}
}
路径操作怎么拆：query_path 和 update_path 的循环逻辑
这是最易出错的部分。不能靠记忆模板，得理解“往上跳”的本质：每次把当前节点 u 跳到 top[u]，处理区间 [id[top[u]], id[u]]，再令 u = fa[top[u]]，直到两节点位于同一条链。
关键点：
- 每次 while 循环中，必须保证
dep[top[u]] ≤ dep[top[v]]（即让深的节点先跳），否则链覆盖不全 - 更新/查询时，线段树操作区间是
[min(id[u], id[v]), max(id[u], id[v])]—— 错！正确是分别跳各自的链，每次处理的是[id[top[x]], id[x]] - 忘记在 while 内部交换 u/v 导致逻辑颠倒（比如本该 u 往上跳，结果 v 跳了）
简化版路径查询框架：
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 = max(res, seg.query(1, 1, n, id[top[u]], id[u])); // 示例：路径最大值
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
res = max(res, seg.query(1, 1, n, id[u], id[v]));
return res;
}
重链剖分真正难的不是代码量，而是每一步跳转时对 top、fa、id 三者关系的即时判断。调试时建议打印几组小样例的 top 和 id 值，比对着线段树区间看是否连续、无重叠、无遗漏。
