先说一道题给你一棵n个节点的树边有权问有多少条路径满足路径上所有边权之和不超过k。n能到 1e4 甚至 2e4如果暴力枚举所有点对、再用 LCA 算距离复杂度的数量级是 O(n²logn)到了 1e8 以上就已经开始吃力换成 n5e4 的加强版数据直接就是不可能完成的任务。这时候就该树分治出场了。树分治里最基础也最好用的就是点分治它把统计树上所有路径这种看起来无从下口的问题拆成每次只统计经过某个点的路径再递归处理剩下的子树。很多初学者觉得它难其实无非是找重心 统计 删点 递归这四步只是每一步里都藏着几个容易踩的坑。这篇文章就按这个顺序把点分治从零拆开讲。你不用有任何前置知识只要会 DFS、知道什么是树的子树就能跟着走完整个流程。1. 从一个计数问题说起为什么O(n²)会卡住你先明确我们要解决什么问题。给定一棵树边有权通常非负统计有多少条路径满足路径总长不超过k。路径的两个端点可以是任意两个不同的节点也可以是一个点本身长度为 0一般题目会说明是否计数POJ 1741 这类经典题里单独点路径不算我们后面默认不数。暴力做法最直接枚举所有点对(u, v)通过预处理 LCA 得到dist(u) dist(v) - 2 * dist(lca)再看是否小于等于k。点对数有n * (n-1) / 2个每算一次距离是 O(1) 或者 O(logn)所以总复杂度是 O(n²) 或 O(n²logn)。n1e4 已经要跑 10^8 量级运算极限数据下稳稳超时。换个角度观察会发现树有一个非常适合分治的结构特点任意一条路径要么经过某个节点r要么完全落在r的某一棵子树里。这句话看起来是废话但它就是整个点分治的立足点。如果我们能枚举所有路径的最高点也就是路径两端点在原树中的 LCA那每条路径都可以在它的 LCA 那一层被统计到。问题是 LCA 并不好直接枚举但我们可以反过来选一个节点r先统计所有经过r的路径然后把r从树里删掉剩下若干棵互相独立的子树再对每棵子树递归做同样的事。为什么删掉r是安全的因为任何一条路径如果在某一层没有被统计即没经过该层的r那么它一定完整地存在于某个子连通块里后续递归一定能遇到它。这样设计下每条路径只会被统计一次恰好是在它遇到的第一个、能把它分隔开的节点那一层。这就是点分治不重不漏的根基。但这里有个致命问题r如果选得不好递归的层数会非常深。比如一棵链状的树如果你每次都选端点作为r删掉后剩下的连通块大小还是n-1递归深度变成 O(n)分治就退化成暴力了。所以我们需要一种特殊的选点策略这就是重心的意义。2. 为什么是重心随便选根会把算法做成蜗牛先给重心下个定义。在一个大小为total的连通块里如果删掉节点u后剩下的所有连通块中最大的那一块的大小maxPart[u]最小那u就是这个连通块的重心。通俗点说重心就是把树从中间剪一刀让两边尽可能均衡的那个点。计算方式很直接对每个点比较它各棵子树的大小还有一个向上走的部分——也就是整个连通块去掉以它为根的子树后剩余的部分取最大值maxPart[u] max(儿子子树的最大 size, total - sz[u])其中sz[u]是以某个临时根为准时节点u的子树大小total - sz[u]是因为你在 DFS 时只看到了它的子树它上面那一整块也是删掉它以后会产生的连通块。为什么选重心能保证递归层数是 O(logn)有一个很好的性质树的重心删掉后产生的每个连通块大小都不超过total / 2。证明也不难假设某个连通块大小sz[v] total / 2那么把重心从u换到vmaxPart[v]会更小v的连通块变成了total - sz[v] total / 2而其余的块在删u时已经作为v的兄弟子树存在大小也不超过sz[v]减一与重心让最大块最小矛盾。有了这个性质每次递归进入的子树大小都会至少减半递归深度最多 O(logn)。整棵树上所有递归层的总工作量严格可控这也是点分治名字里分治二字的底气每一次都切在最均衡的位置。一棵树可能有两个重心奇偶情况选任意一个都满足上面的大小限制所以实现时不需要特判只要按maxPart 最小的条件选出一个就行。光知道要找重心还不够写代码时怎么高效找以及对当前连通块的总大小到底该传什么值这其实是新手最容易写错的地方我们放到后面专门讲。先看整体流程。3. 点分治的标准递归流程三步走的骨架点分治的递归函数solve(u)的框架本质上只有四步计算当前连通块的大小total然后在块内找到重心rt。统计所有经过rt且满足条件的路径累加到答案里。把rt标记为已删除防止后续递归时路径再次跨过它。遍历rt的所有未被删除的邻居对每个邻居所在的连通块递归调用solve。用伪代码表示就是这样solve(u): total get_size(u, 0) // 1.先知道这个连通块多大 rt get_root(u, 0, total) // 2.找重心 ans calc(rt, 0) // 3.统计经过 rt 的路径 dead[rt] True // 4.删掉 rt for v in adj[rt]: if not dead[v]: ans - calc(v, w) // 5.容斥减去同一子树内的非法路径 solve(v) // 6.递归处理子树这段伪代码里最需要理解的是第 3 步和第 5 步。calc(rt, 0)干的事情是把当前连通块内所有节点到rt的距离收集起来排序后用双指针统计任选两个点距离和不超过k的路径数量。但它统计出来的并不全是以rt为最高点的合法路径因为同一棵子树内的两个点它们的路径根本不会经过rt却也会被这一层统计到。所以在第 5 步对每个子节点v要再调用一次calc(v, w)这里的w是边权也就是从rt到v的距离。这样calc(v, w)收集到的距离依然是这些子树节点到rt的距离但参与配对的点只会来自v这同一棵子树统计出来的恰好就是刚才多算的那部分。用总数减去所有子树内的非法数剩下的就全部是经过rt的合法路径。理解这个先算全部、再减掉子树内的思想很重要。它本质上用了容斥全集中去掉不合法的子集剩下的就是想要的集合。dead[rt] true这个操作也别小看。它一方面在物理上把问题拆分开了让递归的连通块真正互相独立另一方面它保证我们已经统计过的经过rt的路径在后续递归中永远不会再被碰到。因为后续所有递归都只在dead为 false 的连通块内进行而任何被删掉的点都会在 DFS 时被跳过。4. get_size、get_root、get_dist三个DFS如何分工点分治的代码有很强的套路性核心就是三个 DFS 函数。我们逐个拆开把每行的意图讲清楚。get_size计算当前连通块的大小int get_size(int u, int fa) { sz[u] 1; for (int i head[u]; i; i e[i].next) { int v e[i].to; if (v fa || dead[v]) continue; sz[u] get_size(v, u); } return sz[u]; }这个函数的作用只有一个返回以u为入口的当前连通块的总节点数。注意两个过滤条件v fa防止走回头路dead[v]防止跨越已经被删除的重心。这一步如果漏了dead[v]你会把已经删掉的点也统计进来后续找重心的total就错了整个递归的平衡性都会崩。get_root在连通块里找出重心int rt, mn; void get_root(int u, int fa, int total) { sz[u] 1; maxPart[u] 0; for (int i head[u]; i; i e[i].next) { int v e[i].to; if (v fa || dead[v]) continue; get_root(v, u, total); sz[u] sz[v]; maxPart[u] max(maxPart[u], sz[v]); } maxPart[u] max(maxPart[u], total - sz[u]); if (maxPart[u] mn) { mn maxPart[u]; rt u; } }这里有两个非常关键的细节。第一个是total - sz[u]。total是当前整个连通块的大小sz[u]是以u为根的假想子树的大小。total - sz[u]代表删掉u后它上面那块的大小。只有把这个也纳入maxPart[u]的比较才能保证找出的节点是真重心。第二个是每次调用前必须把mn重置成一个极大值。很多人第一次写点分治 WA 到怀疑人生就是因为mn还是上一次递归的值导致if (maxPart[u] mn)一直不成立rt永远是最开始那个旧值。每次solve开始时记得mn INF。get_dist收集距离序列vectorint vec; void get_dist(int u, int fa, int dist) { vec.push_back(dist); for (int i head[u]; i; i e[i].next) { int v e[i].to; int w e[i].w; if (v fa || dead[v]) continue; get_dist(v, u, dist w); } }这个函数就是把指定起点到当前连通块内所有点的距离收集到一个 vector 里。dist参数是累计距离初始值由calc决定。把三个函数组合起来solve的完整实现如下const int INF 0x3f3f3f3f; void solve(int u) { int total get_size(u, 0); mn INF; get_root(u, 0, total); int cur rt; // 当前连通块的重心 ans calc(cur, 0); // 先加上所有可能路径 dead[cur] true; // 删掉重心 for (int i head[cur]; i; i e[i].next) { int v e[i].to; int w e[i].w; if (dead[v]) continue; ans - calc(v, w); // 容斥减去同一子树内的非法统计 solve(v); // 递归处理该子树 } }为什么get_root之前要先跑一遍get_size因为get_root里需要用到total而这个连通块的大小只能通过实际 DFS 才能拿到。get_root本身也会重新计算sz[]所以两个函数都写了sz[u] 1的初始化它们各自独立维护自己需要的数组值这是套路里允许的冗余。要注意的是递归调用solve(v)前我们已经在solve的循环里对v这棵子树做了容斥ans - calc(v, w)但这个减法只减了重复统计的量并没有递归进去处理子树内部的路径。子树的真正答案是通过solve(v)继续往下拆分的。这里千万不能颠倒顺序先减后递归或者先递归后减在数学上是一样的因为solve(v)只会在dead[cur]为 true 后的连通块里活动不会再次经过cur不会和本层的统计互相干扰。不过实践中强烈的建议是先容斥再递归这样逻辑上更清楚不容易在调试时看岔。5. calc函数的两种写法容斥法与增量法的取舍calc是点分治里干活最重的部分也决定了你能用它解决哪些具体问题。先看最经典的排序双指针容斥写法。排序双指针 容斥POJ 1741 标准解法int calc(int u, int initDist) { vec.clear(); get_dist(u, 0, initDist); sort(vec.begin(), vec.end()); int res 0; int l 0, r (int)vec.size() - 1; while (l r) { if (vec[l] vec[r] k) { res r - l; // 固定 l则 (l1..r) 这些点都能和 l 配对 l; } else { r--; } } return res; }这段双指针的逻辑要仔细想一遍如果vec[l] vec[r] k说明对于当前最小的vec[l]从vec[l1]到vec[r]的所有值都能和它配对满足条件一共r - l对然后l去考虑下一个更小的起点反之则说明当前最大的vec[r]和谁都配不上直接r--。因为序列有序这个过程不会漏配。比如有一组距离vec [0, 2, 3, 5, 7]k 6一开始l0, r40 7 6所以r3。0 5 6答案加3 - 0 3对应 (0,5)、(0,3)、(0,2)然后l1。2 5 6r2。2 3 6答案加2 - 1 1对应 (2,3)l2。l r结束。总共有 4 对满足条件的点对。但注意了calc(rt, 0)得到的这 4 对里面可能有同一棵子树内的点对它们的路径并不经过rt。所以solve里对每个子节点v执行ans - calc(v, w)此时calc(v, w)收集的是从v出发、带着初始距离w的所有子树节点到rt的距离。这些距离组成的序列vec[l] vec[r] k的配对正好就是之前被错误计入的同一子树内点对。这里有个很巧妙的地方calc(v, w)里的w是rt到v的边权所以即便我们在v这棵子树里做 DFS收集到的距离也已经自动变成了相对于rt的距离。这样在同一个k的标准下做减法数值上才是精确抵消的。增量法不需要容斥的另一种思路容斥写法简单直接但它有一个隐含前提vec可以全部收集完再统一排序。有些问题例如要求统计路径长度恰好为某个值的多个查询你希望保留已经处理过的子树的信息这时更常用的做法是增量法// 假设用桶/哈希表记录 previous 集合中每个距离出现的次数 for (int i head[rt]; i; i e[i].next) { int v e[i].to; if (dead[v]) continue; vec.clear(); get_dist(v, rt, e[i].w); for (int d : vec) { // 查询 previous 中是否存在 q - d决定答案 } for (int d : vec) { // 把当前子树的距离加入 previous } }增量法不再做先加全部再减子树的容斥而是每处理一棵子树之前只和之前已经处理过的子树配对所以天然不会有同一子树内部的非法配对。它比容斥更通用尤其适合处理路径长度恰好等于某个值这类查询因为你可以针对每个查询在previous里查k - d是否存在。代价是通常需要额外维护一个 set、哈希表或者值域数组。我的建议是计数类问题先学容斥法因为代码最简洁、最容易一次写对多查询精确长度类问题直接用增量法可以少走弯路。两种写法要都会面试和竞赛里切换起来才不会卡壳。6. 复杂度推演手里的账本要算清楚点分治的复杂度是很多初学者接受不了的不是有很多递归吗怎么算出来那么快我们把账一笔一笔算给你看。先看每一层递归。假设当前递归深度上有一堆连通块大小分别是s1, s2, ..., sm它们的和不超过n。对每个连通块我们要做get_sizeget_root各遍历一遍连通块代价是 O(si)。calc收集距离 O(si)排序 O(si log si)。所以这个深度上总的代价大约是sum(si) sum(si log si)因为 sum(si) O(n)而 sum(si log si) 最多不超过 n log n在 si 均匀时达到上界所以每一层的工作量是 O(n log n) 量级。再看递归层数。由于每次选的都是重心删掉后每个子连通块大小不超过原块的一半所以递归深度是 O(logn)。总复杂度就是O(logn) 层 × 每层 O(n log n) O(n log² n)这里要澄清一个许多教程里含混的说法。经常看到有人说点分治是 O(n log n)严格来说那是在距离统计不排序的前提下才成立比如用计数数组在没有排序的流程里统计或者某些特殊场景。只要你的calc里用了sort通用写法就是 O(n log² n)。两者在 n2e5 以内都能接受但心里要有这笔账不要在别人问复杂度的时候说错。空间上vec是全局复用的任意时刻最多存 O(n) 个距离递归栈深度 O(logn)外加原树本身的邻接表 O(n)。总空间 O(n)。这个复杂度模型也解释了为什么点分治在实际比赛中常被用作树上路径统计的默认解法——和 O(n²) 的暴力相比它把一个平方级问题降到了近似线性对数的级别提升是巨大的。7. 实战避坑WA了七次才总结出的细节点分治框架本身不难难在细节。我自己第一次完整实现时光调 bug 就调了一晚上下面这些坑基本都是踩过一遍的。坑1mn没有初始化重心永远是同一个这个前面提过一次但值得再强调。如果你不在每次get_root之前把mn设为 INF那么第一次递归时rt被设成了某个点后面所有递归里maxPart[u] mn都不成立rt永远不更新。结果就是整棵树从始至终用同一个根做分治复杂度退化成 O(n²)数据一大立刻 TLE。排查方法很简单在每个solve的第一行打一个cout solve: u total total rt rt endl;然后观察递归到的连通块是否在明显变小。如果某一次rt还是根节点 1那大概率就是mn的问题。坑2get_root里的total用的是全局 n 而不是当前连通块大小如果你在第一次递归之后某个子树的大小是 500但get_root里传的total还是整个树的 20000那么total - sz[u]就会算出一堆巨大的上面部分重心的判断直接错乱。记住total必须是当前这个连通块的总大小所以solve开头要先跑get_size拿到真实的total。坑3calc(v, w)的w写成了 0容斥减去的必须是以重心为参照的子树距离序列。如果写calc(v, 0)你收集到的是从v出发、到子树节点的距离而不是到重心的距离减法完全对不上答案会偏大。这个 bug 的特点是对拍才能发现——小数据看起来挺合理但随机树对拍几次就会差出来。坑4dead数组的过滤不完整在get_size、get_root、get_dist三个 DFS 里DFS 循环的continue条件都必须是v fa || dead[v]。少一个dead[v]递归就会穿过已经删除的重心跑到另一个连通块里去收集距离。这种错误往往导致答案偏大因为一个点的距离被收进了多个集合。坑5边权为负时不能用双指针双指针在有序序列上配对的前提是vec[l] vec[r] k时直接累加r - l才成立。如果边权可以是负数序列有序并不能保证单调性下的这个结论成立双指针就失效了。碰到负边权要么换增量法配合平衡树要么想办法偏置所有权值。绝大多数点分治题目边权是非负的但前提不能自动省略。坑6路径计数用 int 会溢出满足条件的点对数量最多接近n * (n-1) / 2n2e5 时这个值约 2e10远超 int。答案变量、calc的返回值必须用long long。我见过不少人在对拍时用 n100 的数据测不出来一到大数据就 WA就是因为 int 静默溢出。坑7链状树递归爆栈get_root的递归深度在最坏情况下可以是链的长度 O(n)n2e5 时某些系统栈会溢出。不同 OJ 的栈大小不一样如果遇到爆栈先检查是不是真的递归过深有些题目可以用编译选项开栈或者换用显式栈模拟。不过大多数情况下题目给的数据不至于让get_root爆栈如果爆了优先怀疑前面几点写错导致递归没被正确分层。对拍是终极武器点分治这种递归型算法肉眼调试非常痛苦。我的习惯是写一个brute()用 O(n²) 暴力枚举点对算答案再写一个数据生成器随机树、链、菊花、二叉完全树各来一批循环 1000 次对拍。只要两次答案不一致就把当前这组数据拿出来在solve和calc里多打印几层信息很快能定位是选重心、统计还是容斥哪一步出了问题。一轮对拍跑完你基本上就把点分治的骨架和细节都焊死在记忆里了。之后再做带点权、带修改、换根、树上博弈相关的更复杂题你回头看这一段也会觉得——当年那个让我挠头的点分治原来真的只是这四步而已。