定义树链剖分Heavy Light DecompositionHLD是一种将树分解成若干条链的方法使得树上任意两点间的路径可以被拆分成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、soncppvoid 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和topcppint 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”为例cppvoid 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]因此子树的修改/查询比路径更简单cppseg.update(dfn[u], dfn[u] sz[u] - 1, w); // 整棵子树加 w复杂度分析预处理两次 DFSO(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 选手必须掌握的算法之一。通过理解重链剖分的本质——让树变得“连续”——许多看似复杂的树上问题都能迎刃而解。
树链剖分入门
定义树链剖分Heavy Light DecompositionHLD是一种将树分解成若干条链的方法使得树上任意两点间的路径可以被拆分成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、soncppvoid 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和topcppint 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”为例cppvoid 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]因此子树的修改/查询比路径更简单cppseg.update(dfn[u], dfn[u] sz[u] - 1, w); // 整棵子树加 w复杂度分析预处理两次 DFSO(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 选手必须掌握的算法之一。通过理解重链剖分的本质——让树变得“连续”——许多看似复杂的树上问题都能迎刃而解。
