树链剖分（Heavy-Light Decomposition, HLD）将树上的路径操作转化为 O(log n) 次区间操作，配合线段树实现高效的树上路径查询与修改。
一、核心思想
Mermaid · 渲染中（下方为源码）
graph TD A[树] --> B[重链剖分] B --> C[重边连成链] C --> D[链上转区间] D --> E["线段树 O(log²n)"]
将树的边分为重边和轻边：
- 重儿子：子树最大的儿子
- 重链：沿重边向下形成的链
性质：从任意节点到根，最多经过 O(log n) 条轻边 → O(log n) 条重链。
1
/ \
2* 3 (* = 重儿子)
/ \
4* 5
/
6*
重链: 1→2→4→6, 3, 5
二、两次 DFS
int[] size, heavy, depth, parent, top, dfn, rank;
int timer = 0;
// 第一次 DFS：求子树大小、重儿子、深度、父节点
void dfs1(int u, int p, int d) {
parent[u] = p;
depth[u] = d;
size[u] = 1;
int maxSub = 0;
for (int v : adj[u]) {
if (v == p) continue;
dfs1(v, u, d + 1);
size[u] += size[v];
if (size[v] > maxSub) {
maxSub = size[v];
heavy[u] = v;
}
}
}
// 第二次 DFS：分配 dfn（重链优先）
void dfs2(int u, int topNode) {
top[u] = topNode;
dfn[u] = ++timer;
rank[timer] = u;
if (heavy[u] == 0) return; // 叶子
dfs2(heavy[u], topNode); // 重儿子先走，同一条链
for (int v : adj[u]) {
if (v == parent[u] || v == heavy[u]) continue;
dfs2(v, v); // 轻儿子开新链
}
}