定义
树链剖分（Heavy Light Decomposition，HLD）是一种将树分解成若干条链的方法，使得树上任意两点间的路径可以被拆分成O(log n)条连续的链段。
借助这种分解，我们可以用线段树等数据结构维护链上的信息，从而高效处理树上的路径修改与查询问题（如路径求和、最大值、最小值等）。
基本概念
首先需要对一棵有根树定义以下概念：
重儿子：对于一个非叶子节点，其子节点中子树大小最大的那个儿子。
轻儿子：除重儿子外的其他子节点。
重边：节点与其重儿子之间的边。
轻边：节点与其轻儿子之间的边。
重链：由连续的重边构成的极大路径。
特别的，一个孤立的轻节点也视作一条长度为1的重链。
模板中需要维护的数组
| 数组名 | 含义 |
|---|---|
fa[u] | 节点 u 的父亲 |
dep[u] | 节点 u 的深度 |
sz[u] | 以 u 为根的子树大小 |
son[u] | u 的重儿子 |
top[u] | u 所在重链的顶端节点 |
dfn[u] | u 的 dfs 序（时间戳），用于线段树下标 |
rk[t] | dfs 序为 t 的节点编号 |
构建过程
第一遍 DFS：求fa、dep、sz、son
cpp
void dfs1(int u, int f) { fa[u] = f; dep[u] = dep[f] + 1; sz[u] = 1; int maxsz = 0; for (int v : G[u]) { if (v == f) continue; dfs1(v, u); sz[u] += sz[v]; if (sz[v] > maxsz) { maxsz = sz[v]; son[u] = v; } } }第二遍 DFS：分配dfn和top
cpp
int cur = 0; // 当前 dfs 序 void dfs2(int u, int tp) { top[u] = tp; dfn[u] = ++cur; rk[cur] = u; if (son[u]) dfs2(son[u], tp); // 优先走重儿子，保持重链连续 for (int v : G[u]) { if (v == fa[u] || v == son[u]) continue; dfs2(v, v); // 轻儿子单独开新链 } }经过这两遍 DFS，我们得到的dfn数组有一个重要性质：每条重链上的节点在 dfs 序中是连续的一段。这使得我们可以用线段树或树状数组维护整条链的信息。
核心操作
1. 路径修改 / 路径查询
以“将 u 到 v 路径上的每个节点加上 w”为例：
cpp
void update_path(int u, int v, int w) { while (top[u] != top[v]) { if (dep[top[u]] < dep[top[v]]) swap(u, v); // 处理 u 所在的整条重链 [dfn[top[u]], dfn[u]] seg.update(dfn[top[u]], dfn[u], w); u = fa[top[u]]; } // 此时 u 和 v 在同一条重链上 if (dep[u] > dep[v]) swap(u, v); seg.update(dfn[u], dfn[v], w); }查询操作类似，只需将update换成query即可。
2. 子树修改 / 子树查询
由于dfn的分配方式保证了一棵子树内的节点在 dfs 序中也是连续的一段（区间[dfn[u], dfn[u] + sz[u] - 1]），因此子树的修改/查询比路径更简单：
cpp
seg.update(dfn[u], dfn[u] + sz[u] - 1, w); // 整棵子树加 w
复杂度分析
预处理：两次 DFS，O(n)
每次路径操作：O(log² n)（线段树 O(log n) × 重链跳转次数 O(log n)）
每次子树操作：O(log n)
例题
1. 洛谷 P3384 【模板】轻重链剖分 / 树链剖分
题目大意：一棵树，支持四种操作：
将 u 到 v 路径上所有节点加 z
求 u 到 v 路径上节点权值和
将 u 的子树内所有节点加 z
求 u 的子树内节点权值和
解法：直接套用上述模板，用线段树维护区间加与区间求和即可。
2. 洛谷 P3178 [HAOI2015] 树上操作
题目大意：单点加、子树加、查询节点 u 到根节点路径上的权值和。
解法：路径查询时，只需一直跳 top 直到 root，累加每条重链的区间和。
3. SPOJ QTREE – Query on a tree
题目大意：两种操作：
修改某条边的权值
查询 u 到 v 路径上边权的最大值
解法：将边权转移到深度较大的子节点上（即每个节点存储它到父节点的边权），然后用树链剖分维护路径上的最大值。注意查询时避开 LCA 的权值。
4. 洛谷 P2146 [NOI2015] 软件包管理器
题目大意：安装一个软件需要将它到根的路径上所有软件安装，卸载一个软件需要将它整棵子树卸载。每次操作输出改变了多少软件的状态。
解法：树链剖分维护每个节点是否安装（0/1）。安装操作即路径赋值 1，卸载操作即子树赋值 0，修改前后查询区间和的变化量。
常见技巧与注意事项
边权与点权：处理边权时，通常将边权存到深度较大的那个点上，查询路径时排除 LCA 的点权。
换根：树链剖分不直接支持换根，但可以通过分类讨论将任意根转化为原根下的操作。常用技巧：根据 LCA 的位置判断。
动态树（LCT）：如果树是动态变化的（加边、删边），树链剖分不再适用，需要换用 Link-Cut Tree。
与其他数据结构结合：线段树只是其中一种选择，根据题目需要可以换成树状数组、主席树、平衡树等。
总结
树链剖分将树上问题转化为序列问题，是处理静态树路径查询与修改的利器。它代码量适中，思维难度不高，是 OI 选手必须掌握的算法之一。
通过理解重链剖分的本质——让树变得“连续”——许多看似复杂的树上问题都能迎刃而解。
