如果你学过一段时间的算法竞赛，或者刷过不少树相关的题目，大概率会遇到一类问题：给你一棵 n 个节点的树，问所有点对之间满足某个距离条件的数量、是否存在点对距离等于 k、或者求最小最大距离之类。比如最经典的：给定一棵带边权的树，统计距离不超过 k 的点对有多少个。暴力做法是枚举所有点对，O(n^2) 甚至再带个 log，n 到 1e5 的时候基本必挂。
我第一次看到“点分治”这三个字，心里想的是：树又不是数组，怎么分治？后来硬着头皮看了好几篇博客，又手写了无数遍，才慢慢悟出来，点分治本质上就三板斧：找重心、统计经过当前重心的答案、递归进子树继续处理。这篇文章我会把这三板斧掰开揉碎，配合完整代码和踩坑记录，尽量让你看完就能上手写。
1. 点分治到底在解决什么问题
1.1 先从一道最经典的题说起
假设题目是这样的：给你一棵 n 个节点的树，每条边有一个正整数边权，给定一个整数 k，问树上有多少对点 (u, v) 满足 u < v 且 u 到 v 的距离不超过 k。
这个问题的“距离”指的是两个点之间唯一路径上的边权之和。如果 n 只有 1000，那直接用 Floyd 思想暴力跑一下就行：枚举每个点作为起点，DFS 整棵树求距离，再数一数有多少个距离小于等于 k。复杂度 O(n^2)，在 n = 1e5 时完全不可行。
你可能会想到用树形 DP，但路径统计问题里，路径可以跨越两个不同子树，DP 的状态会变得非常复杂，尤其是统计数量而不是最大最小值时，几乎没法只靠一次 DFS 搞定。
这时候点分治就派上用场了。它的核心思路是：把树拆成很多小块的“分治结构”，每次只考虑经过某一个特殊点的路径，剩下的路径全都递归到子树里处理。听起来很抽象，但拆开之后就很简单了。
1.2 路径的无非两类：经过“某个点”或不经过
我们随便抓一个点 root 出来，把树看成一棵以 root 为根的有根树。那么树上任意一条路径 (u, v) 只有两种情况：
- 路径经过了 root，也就是说 u 和 v 分别在 root 的两个不同子树里，或者其中一个就是 root 本身。
- 路径不经过 root，那么它完全落在 root 的某一个子树内部。
这个分类是树路径问题的经典切入点。如果我们能把“经过 root”的所有路径全部统计完，然后把 root 这棵树砍掉，剩下的每一棵子树都是独立的小树，继续递归处理，那所有路径是不是就都被覆盖了？
这个思路本身没问题，但有一个致命伤：如果每层都选一个随便的点做 root，递归的深度可能很大。比如树退化成一条链，每次选链头作为 root，那么每次只能把链分掉一个点，剩下的还是长链，总复杂度会退化成 O(n^2)。
所以必须选一个足够“均衡”的点来分，这就是重心。
1.3 为什么重心能让分治变快
树的重心有一个非常好的性质：删除重心之后，剩余的所有连通块大小都不超过原树大小的一半。
这保证了每次递归的规模至少减半。假设当前这一层的总时间复杂度是 O(n)（找重心、统计路径都是线性遍历一遍当前块），那么总复杂度满足：
T(n) = 2 * T(n/2) + O(n) = O(n log n)
如果是链、菊花图或者其他任何形态，这个递归深度都严格受控在 O(log n) 级别。这就是点分治性能的根基。
所以点分治的本质可以概括成一句话：通过不断找重心，把树上的路径问题拆成“经过重心”和“不经过重心”两个子问题，再用递归把它们分别解决。
2. 前置知识：重心、DFS、复杂度推导
2.1 怎么找树的重心
先明确定义：在一个无根树中，删除某个节点 x 之后，剩下的所有连通块中，最大的连通块大小记为 mx[x]。在所有节点中，mx[x] 最小的那个 x 就是树的重心。
根据这个定义，找重心很简单。我们可以任选一个点作为 dfs 的根，先计算出每棵子树的节点数量 sz[u]。假设整棵树的节点数是 total，那么删除 u 之后，剩下的连通块分为两部分：
- u 的所有儿子对应的子树，大小分别是 sz[v]；
- “父亲方向”的那一块，大小是 total - sz[u]。
所以 mx[u] 就是所有 sz[v] 和 total - sz[u] 的最大值。找出 mx[u] 最小的点即可。
这个过程中有一个很容易出错的地方：total 必须是你当前正在处理的那个连通块的总大小，而不是整棵原树的总大小。因为点分治在递归过程中会不断的把重心标记为“已删除”，后续每一层的“树”其实是原树的一个连通块，所以每次递归进去都必须重新算一次 total。
2.2 重心的性质：每次至少砍掉一半
为什么重心能让总规模减半？这里给一个直观的证明。
假设重心是 c，删除 c 后最大的连通块大小是 S。如果 S > total / 2，那么这个大连通块一定存在一个与 c 相邻的节点 p，使得把重心从 c 移动到 p 之后，原来的“父亲块”大小会变成 total - S，而新的最大连通块大小至少会小于 S。这与 c 是重心的定义矛盾，所以 S <= total / 2。
简单理解就是：如果有一个子树特别大，重心一定就往那个子树方向挪，直到所有方向的大小都相对均衡。这个性质让点分治的递归深度稳定在 O(log n)。
2.3 需要具备的基础代码能力
想直接上手点分治，至少需要掌握以下几样东西：
- 用邻接表或者 vector 存图，能写链式前向星更好。
- 会写不带递归标记的 DFS 遍历树，能正确计算子树大小。
- 了解递归函数的调用栈，知道为什么要用 del 数组标记已删除的点。
如果你这些都熟练，那点分治本身没有太多新概念，都是这些基础操作组合起来的。
2.4 复杂度推导：为什么总复杂度是 O(n log n)
点分治每一层要做的事情包括：
- 遍历当前连通块，计算子树大小、找重心，复杂度 O(m)，m 是当前块的大小。
- 从重心出发，收集点集距离、排序、双指针扫描统计答案，复杂度 O(m log m)。
- 递归进入删除重心后的各个连通块。
关键点在于，每一层的所有连通块大小加起来等于 n，所以每一层的总复杂度是 O(n log n)（因为排序）。而递归深度最多 O(log n) 层，所以最终复杂度是 O(n log^2 n)。
一些优化场景下可以用桶代替排序，把单层变成 O(n)，总复杂度降到 O(n log n)。但竞赛中 O(n log^2 n) 已经能通过绝大多数 1e5 级别的题了，先掌握通用写法最要紧。
3. 点分治的三板斧：找重心、统计、递归
3.1 找重心的代码实现（含 total 处理）
这一步我的写法比较固定，用两个 DFS 函数：
第一个函数 dfs_size 负责算出以传入点为根的子树大小，注意经过 del 数组找过的点要跳过，因为那些点已经被删掉了，不再属于当前连通块。
void dfs_size(int u, int fa) { sz[u] = 1; for (int i = head[u]; i; i = nxt[i]) { int v = to[i]; if (v == fa || del[v]) continue; dfs_size(v, u); sz[u] += sz[v]; } }第二个函数 dfs_root 负责计算每个点的 mx[u]，同时维护重心 rt。
void dfs_root(int u, int fa, int total) { mx[u] = total - sz[u]; // 先算父亲方向的块 for (int i = head[u]; i; i = nxt[i]) { int v = to[i]; if (v == fa || del[v]) continue; dfs_root(v, u, total); mx[u] = max(mx[u], sz[v]); } if (mx[u] < mx[rt]) rt = u; }你可能会问，为什么 dfs_root 里可以直接用 sz[v]？因为我们是先做 dfs_size 遍历了一遍整个连通块，当时以传入 dfs_size 的 u 作为根。在那一轮 DFS 中，每个节点的父子关系已经固定了。所以 dfs_root 里枚举到的 v，就是 v 这个节点在那一棵“遍历树”中的子树大小，这个值是正确的。
完整的找重心入口长这样：
void get_centroid(int start) { dfs_size(start, 0); total = sz[start]; rt = 0; mx[0] = 0x3f3f3f3f; dfs_root(start, 0, total); }调用之后，rt 就是当前连通块的重心。
3.2 统计“经过重心”的路径
统计是点分治里最灵活的部分，不同题目有不同统计方式，我这里给出最经典的“距离不超过 k 的点对数量”的做法。
首先从重心 rt 出发，DFS 收集所有点到 rt 的距离，存进 dist 数组：
void dfs_collect(int u, int fa, int d) { dist[++cnt] = d; for (int i = head[u]; i; i = nxt[i]) { int v = to[i]; if (v == fa || del[v]) continue; dfs_collect(v, u, d + w[i]); } }然后写一个 calc 函数，它的作用是：传入起点 u 和一个初始距离 d，收集 u 能到达的所有点的距离，然后统计有多少对点距离之和不超过 k。
int calc(int u, int d) { cnt = 0; dfs_collect(u, 0, d); sort(dist + 1, dist + cnt + 1); int res = 0; int l = 1, r = cnt; while (l < r) { if (dist[l] + dist[r] <= k) { res += r - l; l++; } else { r--; } } return res; }这个双指针统计的原理是：排序之后，枚举左端点 l，找满足 dist[l] + dist[r] <= k 的最大右端点 r，那么 l+1 到 r 这 r-l 个点都可以和 l 组成合法点对。
需要注意的是，这个统计会把同一棵子树里的点对也算进去。我们在后面通过容斥来修正。
3.3 分治主函数：把答案加起来，再减掉重复
主函数 divide 是点分治的核心入口。流程非常固定：
- 找到当前连通块的重心 rt。
- 用 calc(rt, 0) 统计整块内经过 rt 的路径数量，加到答案里。
- 标记 del[rt] = true，表示重心已经被删除。
- 遍历 rt 的所有邻边，对每个尚未被删除的邻居 v，先执行 ans -= calc(v, w[i])，然后递归 divide(v)。
void divide(int u) { get_centroid(u); ans += calc(rt, 0); del[rt] = true; for (int i = head[rt]; i; i = nxt[i]) { int v = to[i]; if (del[v]) continue; ans -= calc(v, w[i]); divide(v); } }我认识很多人第一次看这个容斥都不太理解，这里我详细讲一下。
假设重心是 rt，点 a 和点 b 都在 rt 的同一个儿子 v 的子树里。在 calc(rt, 0) 中，dist[a] = d(a, rt)，dist[b] = d(b, rt)。如果 d(a, rt) + d(b, rt) <= k，这两个点会被统计为合法点对。但是实际上，a 和 b 的路径并没有经过 rt，它俩的路径完全在 v 的子树内部。所以这两个点应该在后续递归到 v 子树时再被统计，而现在统计就重复了。
怎么去掉重复呢？对每个儿子 v，调用 calc(v, w(rt, v))，这会收集以 v 为起点，初始距离为边权的所有距离。此时收集到的每个点的距离是 d(x, rt)，因为 d(x, v) + w(rt, v) = d(x, rt)。于是 calc(v, w) 统计出的是：“来自 v 子树、且到 rt 的距离之和 <= k”的点对。这些点对全部都是刚才 calc(rt, 0) 里统计过的“非法重复项”。所以我们在整块答案里减掉即可。
减完之后，再递归 divide(v)，在 v 的子树里重新找重心，继续统计不经过 rt 的那些路径。这样所有路径刚好都被统计一次，没有遗漏，也没有重复。
3.4 不同题目下统计方式的变化
点分治的框架是固定的，但 calc 部分会根据题目变化：
- 统计距离等于 k 的点对：可以把距离塞进哈希表或者桶里，枚举一个距离，查 k - dist 是否存在。
- 统计距离不超过 k 的数量：排序 + 双指针。
- 求距离最近的点对：可以用桶记录最小距离，或者使用类似启发式合并的方式。
- 求路径乘积、路径异或等某些特殊条件：选择合适的数据结构来维护即可。
所以学点分治，重点不是背 calc 的代码，而是理解“为什么在重心层统计、为什么容斥、怎么根据题目设计统计方式”。
4. 完整代码：统计树上距离不超过 k 的点对数量
4.1 可直接运行的 C++ 完整代码
下面的代码用链式前向星存图，经过我多次测试，逻辑清晰，适合作为模板。题目数据范围如果比较大，建议在 main 里加一句防止递归爆栈的语句（Windows 上通常不行，Linux 下可以）。
#include <bits/stdc++.h> using namespace std; const int N = 100010; const int INF = 0x3f3f3f3f; struct Edge { int v, w, nxt; } e[N * 2]; int head[N], tot; int n, k; long long ans; void add_edge(int u, int v, int w) { e[++tot] = {v, w, head[u]}; head[u] = tot; } bool del[N]; int sz[N], mx[N], dist[N], cnt_dist; int rt, total; void dfs_size(int u, int fa) { sz[u] = 1; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v; if (v == fa || del[v]) continue; dfs_size(v, u); sz[u] += sz[v]; } } void dfs_root(int u, int fa, int total) { mx[u] = total - sz[u]; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v; if (v == fa || del[v]) continue; dfs_root(v, u, total); mx[u] = max(mx[u], sz[v]); } if (mx[u] < mx[rt]) rt = u; } void dfs_collect(int u, int fa, int d) { dist[++cnt_dist] = d; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].v; if (v == fa || del[v]) continue; dfs_collect(v, u, d + e[i].w); } } int calc(int u, int d) { cnt_dist = 0; dfs_collect(u, 0, d); sort(dist + 1, dist + cnt_dist + 1); int res = 0; int l = 1, r = cnt_dist; while (l < r) { if (dist[l] + dist[r] <= k) { res += r - l; l++; } else { r--; } } return res; } void divide(int u) { dfs_size(u, 0); total = sz[u]; rt = 0; mx[0] = INF; dfs_root(u, 0, total); ans += calc(rt, 0); del[rt] = true; for (int i = head[rt]; i; i = e[i].nxt) { int v = e[i].v; if (del[v]) continue; ans -= calc(v, e[i].w); divide(v); } } int main() { scanf("%d%d", &n, &k); for (int i = 1; i < n; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); add_edge(u, v, w); add_edge(v, u, w); } divide(1); printf("%lld\n", ans); return 0; }4.2 核心步骤逐行解释
在 divide(1) 中，第一次进入时，整棵树都是一个连通块。dfs_size(1, 0) 会算出所有节点的 sz。这里需要注意，如果原树很大且递归层数较深，第一次 dfs_size 的递归深度可能等于树的深度，所以在极端链形数据下，有些评测环境会爆栈，需要人工扩栈或改成非递归。不过这属于后话，先保证逻辑正确。
算出 total 后，dfs_root 从传入点出发，遍历整个连通块，用 mx 选出重心。由于我们每次用 mx[0] = INF 来初始化，rt 一定会在遍历中被更新。
calc(rt, 0) 把重心到周围所有点的距离收集起来，排序后用双指针统计。此时 dist 数组里包含重心本身（距离为 0）。如果题目要求统计 u < v 的点对，自己和自己不会被统计，因为双指针要求 l < r；重心和其他点组合则是合法的“路径经过重心”的点对，没问题。
标记 del[rt] 之后，遍历邻居。calc(v, e[i].w) 中的初始距离是边权，相当于把 dist[x] = w + d(v, x)，正好等于 x 到重心的距离。这个减法是整个模板里最容易写错的一步。
4.3 手动测试一组数据
构造一棵 4 个点的树：
1-2 边权 1 1-3 边权 2 2-4 边权 3 k = 3点对距离：
- (1,2): 1
- (1,3): 2
- (1,4): 4
- (2,3): 3
- (2,4): 3
- (3,4): 5
距离不超过 3 的点对有 (1,2)、(1,3)、(2,3)、(2,4)，共 4 对。上面代码跑出来答案应该是 4。
你可以在本地多随机构造几棵小树，用 O(n^2) 暴力对拍，来验证模板的正确性。这也是我推荐的学习方式：先会套板子，再慢慢理解容斥。
5. 常见问题与避坑指南
5.1 找重心时 total 算错了
这是新手最容易踩的坑。在递归进入子树时，当前连通块的节点数量并不是原树的 n，而是删掉上一层重心后形成的连通块大小。
一个典型错误写法如下：
void divide(int u) { // 错误：直接用 n 当 total dfs_root(u, 0, n); ... }如果当前连通块不是原树，用 n 计算 total - sz[u] 就会出现负数或偏大的值，导致重心找错，分治效率退化。
正确做法就是像我上面那样，先用 dfs_size 算出当前连通块的 sz，然后用 sz[start] 作为 total。每次进入 divide 都必须重新计算，不能偷懒。
5.2 忘记标记 del 导致统计越界
del 数组的作用是“这个点已经被当作重心删掉了”。在点分治后续的 dfs_size、dfs_root、dfs_collect 中，都要跳过 del 的点，否则会沿着已经被删掉的点跑到别的连通块里去，导致答案错误或者无限递归。
我调试时喜欢在 divide 开头打一句：
printf("divide %d, block size %d\n", u, total);来确认每次递归的点 u 是否仍然属于当前连通块。如果发现递归跑到了一个之前标记为 del 的节点上，说明要么 del 没写对，要么遍历邻边时没跳过 del。
5.3 容斥时为什么是 ans -= calc(v, w)
很多初学者照着模板抄，却不知道为什么 calc(v, w) 能去掉重复。
我建议你自己动手画一棵树，比如一条链 1-2-3，重心是 2。calc(2,0) 会把 (1,3) 距离 2 统计进来，也会把 (1,2) 距离 1 和 (2,3) 距离 1 统计进来。递归到儿子 1 时，calc(1, w) 会收集 1 和到 2 的距离 1，但由于 del[2] = true，实际上只会收集到 1 本身，所以没有点对可以构成，减不掉什么。递归到儿子 3 同理。所以整块答案最终是 3 个点对，正好正确。
如果树是 1-2-3-4，重心是 2 或 3，你按代码手算一遍，就能体会到 calc(v, w) 收集的点对，恰好是 calc(rt,0) 里那些“起点终点都在同一子树”的路径。
5.4 双指针统计时允许点对相同怎么办
有些题目允许路径的起点和终点相同，比如统计点对 (u, v) 且可以 u == v，这时路径长度为 0，只要边权非负，几乎所有点对都合法，问题本身失去了意义。所以绝大多数题目都是 u < v，或者统计的是路径数量，自己到自己不算。
如果你的题目特殊，比如统计“距离小于等于 k 的路径数量（包括长度为 0 的路径）”，那需要在 calc 里额外加上 dist 数组的长度，因为每个点到自己也是一条路径。这个思路和普通点对统计略有差异，需要根据题面灵活处理。
5.5 递归爆栈问题
点分治的递归深度虽然是 O(log n)，但每次找重心前的 dfs_size / dfs_root 在链形树上可能递归深度达到 n。很多评测系统默认栈空间比较小，n = 1e5 时容易爆。
解决方案有几种：
- 在 Linux 下用
ulimit -s unlimited或者程序开头加#pragma comment(linker, "/STACK:102400000,102400000")（仅某些编译器有效）。 - 自己实现栈模拟 DFS，不过代码复杂度会上升。
- 如果数据不极端，也可以试着用
std::function包装递归函数，同时尽量让存储结构紧凑，减小栈帧。
我自己的经验是，竞赛环境下大多数题目不会专门卡递归栈，但如果你在力扣或者某些在线平台提交，最好先了解一下平台的栈限制。
6. 实战经验：怎么判断一道题要用点分治
6.1 题目特征的快速判断
点分治的适用场景非常清晰，满足这几点就可以考虑：
- 问题涉及“树上所有点对”或者“任意两点之间的路径”。
- 路径相关条件可以通过距离、权重、位运算等描述。
- n 的范围在 1e5 以上，暴力枚举点对过不了。
- 树形 DP 很难维护“跨子树”的信息。
比如：
- 统计树上距离等于 k 的路径数量。
- 统计距离小于等于 k 的点对数量。
- 求树上点对距离的最小值。
- 统计路径边权异或和等于 k 的点对。
这些基本就是点分治的经典题型。
6.2 一个简单的判断思路
如果你拿到一道题，觉得“从每个点出发 DFS 一次就能做，但会超时”，那大概率可以用点分治优化。因为点分治本质上就是把所有点对按照“路径经过哪一层的重心”来分组统计。
如果你发现树形 DP 里需要维护“不同子树之间两两组合”的信息，而且合并很麻烦，往往也可以用点分治把“跨子树”转化成“经过重心的路径”，从而统一处理。
6.3 点分治的进阶：点分树
当你完全掌握了点分治之后，可以再去了解一下点分树，也叫动态点分治。它把每一层分治时找到的重心连成一棵树，利用重心分治结构支持单点修改、树上距离查询等动态操作。很多带修改的树上路径问题最终会用到点分树。
但我的建议是先别急着学点分树，先把静态点分治的模板写到滚瓜烂熟，尤其是容斥那一步，最好做到能不看代码手写出来，再去碰动态版本。否则很容易被“重心连树”这个概念绕晕。
7. 一个小技巧：用对拍验证模板
学习点分治的过程中，最有效的验证方法就是写一个 O(n^2) 的暴力程序，随机生成树，然后对拍。
我自己学的时候，写了一个生成随机树的脚本，然后用下面这样的暴力函数作为基准：
long long brute(int n, int k, vector<tuple<int,int,int>>& edges) { vector<vector<int>> g(n+1); for (auto &[u,v,w] : edges) { g[u].push_back(v); g[v].push_back(u); } long long res = 0; for (int i = 1; i <= n; i++) { // 从 i 出发 DFS 求到所有点的距离 vector<int> dist(n+1, -1); queue<int> q; q.push(i); dist[i] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) if (dist[v] == -1) { dist[v] = dist[u] + 1; // 边权为 1 的情况 q.push(v); } } for (int j = i+1; j <= n; j++) { if (dist[j] <= k) res++; } } return res; }注意如果边权不是 1，把边权也存进去，用 Dijkstra 或者 BFS 处理权值。对拍时随机生成 n 在 1 到 200 的树，多跑几万组，基本能保证模板不出错。
对拍最大的好处是能把“逻辑错误”和“实现错误”分开。如果你的点分治输出和暴力不一致，不要急着看模板，先造一个小数据，手动模拟一遍分治过程，找出是容斥错了还是重心错了。这个过程虽然烦，但真的能让你的理解上一个台阶。
