1. 树链剖分到底在解决什么问题第一次接触树链剖分的人大概率是被“轻重链”“dfs序”“线段树维护”这一串名词劝退的。我当初也是看了一堆博客每篇都在讲“把树剖成链”但没人告诉我为什么要剖、剖完之后能干什么。后来刷到洛谷P3384这道模板题硬着头皮把板子敲了五遍才真正理解它的价值。简单说树链剖分解决的是树上路径操作和子树操作的统一维护问题。你有一棵树每个节点有权值现在要你支持四种操作路径上加值、路径上求和、子树上加值、子树上求和。如果没有树链剖分你得对每种操作单独设计算法路径操作和子树操作的维护方式完全不同代码量大且容易出错。树链剖分的核心思路是通过两次DFS把树上的节点重新编号使得任意一条路径可以被拆成O(log n)段连续区间同时任意一棵子树的所有节点编号也是连续的。这样一来路径操作和子树操作都变成了线段树上的区间操作一套线段树就能同时搞定两种需求。这个“重新编号”的过程就是剖分。具体来说每个节点选一个“重儿子”——子树最大的那个孩子然后从根节点出发沿着重儿子一路往下走形成一条“重链”。轻儿子则各自作为新重链的起点。剖分完成后每条重链上的节点编号是连续的每棵子树的节点编号也是连续的。这两个性质是树链剖分能工作的基石缺一不可。适合谁来学如果你已经掌握了线段树的基本操作区间加、区间求和并且能熟练写DFS遍历树那树链剖分就是你的下一个必点技能。它不算特别难但细节多第一次写很容易在各种边界条件上翻车。这篇文章我会把板子拆开揉碎把每个参数的含义、每步操作的理由都讲清楚让你不仅能抄还能改。2. 核心思路拆解与方案选型2.1 为什么是“轻重链”而不是随便剖剖分的方式有很多种比如随机剖、按子树大小剖、按深度剖。树链剖分选择“重儿子”作为剖分依据背后有严格的复杂度保证。定义重儿子为子树最大的孩子轻儿子为其他孩子。从任意节点走到根节点经过的轻边数量不超过O(log n)条。这个结论的证明很直观每经过一条轻边当前子树大小至少翻倍所以最多经过log n条轻边。而重链上的边是连续的所以任意路径被拆成的区间数也是O(log n)级别。如果随便剖比如每次选第一个孩子作为重儿子那最坏情况下树退化成一条链路径操作就退化成O(n)了。所以“按子树大小选重儿子”不是随便定的它是保证复杂度的关键。你在写代码的时候第一次DFS必须正确计算出每个节点的子树大小否则后面的剖分全是错的。2.2 两次DFS各自在做什么整个剖分需要两次DFS分工非常明确第一次DFS负责计算四个信息父节点fa、深度dep、子树大小siz、重儿子son。这四个信息是第二次DFS的基础。注意第一次DFS是普通的树遍历从根节点出发递归到每个孩子回溯时累加子树大小同时记录最大子树对应的孩子作为重儿子。第二次DFS负责分配新的编号id同时记录每个节点所在重链的顶端top。第二次DFS的顺序很讲究必须先递归重儿子再递归轻儿子。为什么因为我们要保证同一条重链上的节点编号连续。如果先递归轻儿子重链就被打断了连续性就没了。这个顺序是树链剖分的灵魂写反了整个算法就废了。2.3 线段树为什么能同时管路径和子树剖分完成后我们得到了一棵“新树”——其实就是原来的树节点按新编号排成的一个数组。这个数组有两个关键性质重链连续同一条重链上的节点编号是连续的。子树连续同一棵子树的所有节点编号也是连续的。子树连续是因为第二次DFS本质上是DFS序DFS序的经典性质就是子树连续。重链连续是因为我们优先递归重儿子所以重链上的节点在DFS序中紧挨在一起。有了这两个性质路径操作就可以拆成若干段重链区间每段用线段树维护子树操作直接对应一个区间也用线段树维护。一套线段树两种操作完美统一。3. 板子逐行拆解与实操要点3.1 第一次DFS计算siz和son先看代码我习惯用链式前向星存图这样比vector快一些尤其是在节点数大的时候。void dfs1(int u, int f, int d) { fa[u] f; dep[u] d; siz[u] 1; int maxson -1; for (int i head[u]; i; i e[i].next) { int v e[i].to; if (v f) continue; dfs1(v, u, d 1); siz[u] siz[v]; if (siz[v] maxson) { maxson siz[v]; son[u] v; } } }这段代码有几个细节容易翻车。第一maxson初始化为-1不是0。因为子树大小至少是1如果初始化为0当所有孩子子树大小都大于0时没问题但逻辑上-1更严谨。第二siz[u] 1必须在递归之前赋值因为要累加孩子的子树大小。第三判断重儿子时用的是siz[v] maxson不是。如果有多个孩子子树大小相同选第一个遇到的即可用可以保证这一点。注意如果你的树节点数超过1e5递归深度可能爆栈。两个解决办法一是手动开大栈空间二是改成非递归写法。我一般直接在代码开头加#pragma comment(linker, /STACK:102400000,102400000)Windows下管用Linux下用ulimit -s调整。3.2 第二次DFS分配id和topvoid dfs2(int u, int t) { id[u] cnt; rk[cnt] u; top[u] t; if (!son[u]) return; dfs2(son[u], t); for (int i head[u]; i; i e[i].next) { int v e[i].to; if (v fa[u] || v son[u]) continue; dfs2(v, v); } }这段代码的关键点在于递归顺序。先递归son[u]并且把top传下去这样重链上的节点共享同一个top。然后再遍历其他孩子每个轻儿子自己作为新重链的起点所以top传的是v自己。rk数组是id的反向映射rk[cnt] u表示新编号为cnt的节点是原节点u。这个数组在初始化线段树的时候要用因为线段树维护的是新编号对应的权值而原权值是存在原节点上的。实操心得id和rk这两个数组一定要分清。id[u]是节点u的新编号rk[i]是新编号i对应的原节点。我见过太多人在这两个数组上搞混导致线段树初始化的时候把权值放错了位置。3.3 线段树部分区间加与区间求和线段树就是标准的懒标记线段树支持区间加和区间求和。这里我直接给一个封装好的结构体版本比全局数组清爽很多。struct SegTree { int sum[MAXN 2], lazy[MAXN 2]; void pushup(int rt) { sum[rt] sum[rt 1] sum[rt 1 | 1]; } void pushdown(int rt, int l, int r) { if (lazy[rt]) { int mid (l r) 1; sum[rt 1] lazy[rt] * (mid - l 1); sum[rt 1 | 1] lazy[rt] * (r - mid); lazy[rt 1] lazy[rt]; lazy[rt 1 | 1] lazy[rt]; lazy[rt] 0; } } void build(int rt, int l, int r, int* val) { if (l r) { sum[rt] val[l]; return; } int mid (l r) 1; build(rt 1, l, mid, val); build(rt 1 | 1, mid 1, r, val); pushup(rt); } void update(int rt, int l, int r, int L, int R, int v) { if (L l r R) { sum[rt] v * (r - l 1); lazy[rt] v; return; } pushdown(rt, l, r); int mid (l r) 1; if (L mid) update(rt 1, l, mid, L, R, v); if (R mid) update(rt 1 | 1, mid 1, r, L, R, v); pushup(rt); } int query(int rt, int l, int r, int L, int R) { if (L l r R) return sum[rt]; pushdown(rt, l, r); int mid (l r) 1, res 0; if (L mid) res query(rt 1, l, mid, L, R); if (R mid) res query(rt 1 | 1, mid 1, r, L, R); return res; } };build函数接收的val数组就是按新编号排列的权值数组也就是val[id[u]] 原权值[u]。这个映射关系在dfs2之后建立千万别搞反。3.4 路径操作拆链的核心逻辑路径操作是树链剖分最精髓的部分。给定两个节点u和v我们要对它们之间的路径进行操作。核心思路是每次让所在重链顶端深度更大的那个节点往上跳跳到它重链顶端的父节点同时处理这一段重链的区间。重复这个过程直到两个节点在同一条重链上。void pathUpdate(int u, int v, int w) { while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); seg.update(1, 1, n, id[top[u]], id[u], w); u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); seg.update(1, 1, n, id[u], id[v], w); }这段代码有几个关键点。第一比较的是dep[top[u]]和dep[top[v]]不是dep[u]和dep[v]。因为我们要跳的是重链顶端更深的那条链。第二跳完之后u fa[top[u]]注意是跳到重链顶端的父节点不是跳到重链顶端的父节点的重儿子。第三当两个节点在同一条重链上时深度较小的那个节点编号也较小因为重链上深度递增对应编号递增所以直接取id[u]到id[v]的区间即可。常见错误有人把while循环里的swap条件写成dep[u] dep[v]这是错的。必须比较top的深度因为我们要处理的是整条重链不是单个节点。3.5 子树操作一行代码搞定子树操作简单到令人发指因为子树在DFS序中就是连续的一段区间。以u为根的子树节点编号范围是[id[u], id[u] siz[u] - 1]。所以子树加就是seg.update(1, 1, n, id[u], id[u] siz[u] - 1, w);子树求和同理seg.query(1, 1, n, id[u], id[u] siz[u] - 1);就这么简单。这也是树链剖分最爽的地方——路径操作那么复杂子树操作却只要一行。如果你只维护子树操作甚至不需要树链剖分普通的DFS序就够了。但树链剖分把两者统一了这才是它的价值所在。4. 完整实操流程与参数计算4.1 建图与初始化假设我们有n个节点m条边树的话mn-1每个节点有一个初始权值。建图用链式前向星int head[MAXN], cnt_edge 0; struct Edge { int to, next; } e[MAXN 1]; void addEdge(int u, int v) { e[cnt_edge] {v, head[u]}; head[u] cnt_edge; }注意边数组要开两倍因为树是无向图每条边要存两次。head数组初始化为0cnt_edge从1开始这样0可以表示空指针。读入权值后先跑dfs1(1, 0, 1)再跑dfs2(1, 1)。然后构建val数组for (int i 1; i n; i) { val[id[i]] w[i]; } seg.build(1, 1, n, val);这里w[i]是原节点i的权值val是按新编号排列的权值。顺序千万不能反。4.2 四种操作的调用方式洛谷P3384要求支持四种操作对应调用如下操作编号操作内容调用方式1路径u到v加wpathUpdate(u, v, w)2路径u到v求和pathQuery(u, v)3子树u加wseg.update(1,1,n,id[u],id[u]siz[u]-1,w)4子树u求和seg.query(1,1,n,id[u],id[u]siz[u]-1)路径求和的代码和路径加几乎一样只是把update换成query并且累加结果int pathQuery(int u, int v) { int res 0; while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); res seg.query(1, 1, n, id[top[u]], id[u]); u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); res seg.query(1, 1, n, id[u], id[v]); return res; }注意取模的问题。洛谷P3384要求对某个数取模所有加法和求和都要取模。我建议在pushup和pushdown里就取模而不是在最后取这样可以避免中间结果溢出。4.3 参数计算与复杂度分析树链剖分的时间复杂度是O(n log² n)。为什么是log²因为路径操作最多拆成O(log n)段重链每段用线段树操作是O(log n)所以总的是O(log² n)。子树操作是O(log n)因为只有一段区间。空间复杂度是O(n)线段树开4倍空间链式前向星开2倍空间其他数组都是O(n)。实操心得如果你的n是1e5级别O(n log² n)完全够用。但如果n是1e6可能需要考虑更高效的写法比如用树状数组代替线段树或者用全局平衡二叉树。不过对于模板题来说线段树版本足够了。5. 常见问题与排查技巧实录5.1 答案错误先查这三个地方树链剖分写挂了90%的问题出在以下三个地方第一dfs2的递归顺序。必须先递归重儿子再递归轻儿子。如果先递归轻儿子重链就不连续了路径操作会拆出错误的区间。检查方法随便找一条重链看看链上节点的id是否连续。第二路径操作的swap条件。必须比较dep[top[u]]和dep[top[v]]不是dep[u]和dep[v]。这个错误非常隐蔽因为有时候答案看起来是对的但在某些路径上会出错。第三线段树初始化时的映射。val[id[i]] w[i]不是val[i] w[id[i]]。搞反了的话线段树维护的权值就全乱了。5.2 运行超时检查递归深度和常数如果TLE了先看递归深度。dfs1和dfs2都是递归n1e5时递归深度可能达到1e5栈空间不够会RE或者TLE。解决办法前面说了开大栈或者改非递归。如果栈没问题但还是TLE检查线段树的常数。pushdown里能少算就少算比如mid - l 1和r - mid可以提前算好。另外链式前向星比vector快建议用链式前向星。5.3 取模问题负数取模的坑洛谷P3384要求对mod取模如果mod不是质数不能用逆元只能老老实实取模。注意C中负数取模还是负数所以每次加法后要(x % mod mod) % mod。我一般写一个内联函数inline int add(int a, int b) { return (a b) % mod; }如果a和b都是取模后的非负数直接加不会溢出的话这样写就够了。但如果a和b可能很大要先取模再相加。5.4 常见问题速查表问题现象可能原因排查方法路径答案偏小dfs2顺序错误检查重链id是否连续子树答案错误siz计算错误检查dfs1中siz累加部分路径答案错误swap条件错误改为比较dep[top]全部答案错误线段树映射反了检查val数组赋值运行超时递归爆栈或常数大开大栈或改非递归取模后为负负数取模未处理加mod再取模避坑技巧写完之后不要急着提交先自己造几组小数据手动模拟。比如一条链、一棵完全二叉树、一棵菊花图这三种形态能覆盖大部分边界情况。手动模拟一遍dfs1和dfs2的结果确认id和top都正确再提交。6. 板子之外的扩展思路树链剖分不仅仅能维护路径和子树它本质上是一种树上的区间映射。任何能用线段树维护的区间操作都能搬到树上。比如路径最大值/最小值把线段树的sum换成max或min即可。路径第k大需要可持久化线段树或者树套树复杂度会上升。动态树如果树的结构会变树链剖分就不够用了需要Link-Cut Tree。另外树链剖分经常和**最近公共祖先LCA**结合使用。求LCA的时候不断跳重链直到两个节点在同一条重链上深度较小的那个就是LCA。这个技巧在路径操作里其实已经用到了只是没有单独拿出来说。如果你已经能熟练默写这个板子下一步可以试试边权树链剖分。边权需要把边权下放到深度较大的节点上然后路径操作时注意不要处理LCA节点的权值。这个变体在比赛中经常出现值得单独练一练。我个人在实际操作中的体会是树链剖分的难点不在代码量而在细节的精确性。每个数组的含义、每个循环的顺序、每个比较的对象都必须清清楚楚。我见过太多人板子抄了十遍还是错就是因为没有理解每一步在干什么。把dfs1和dfs2的每一步都手动模拟一遍把路径操作的跳链过程画出来比抄十遍代码有用得多。