1. 把题目还原清楚男人八题第一题到底要你算什么算法竞赛圈里流传过一个说法叫楼教主的男人八题指的是当年 POJ 上八道公认难啃的题。这八题我前后磕了好几轮第一题就是那道被无数人当作树分治入门试金石的POJ 1741 Tree。它的定位很微妙思路不复杂但第一次见基本写不出来写过一次之后又会觉得它是点分治最干净的模板。所以圈里有个很经典的现象——很多人倒在这题上一整天然后第二天突然开窍从此见到树上点对统计就知道该往哪个方向想。先把题意用一句话说清楚给你一棵 n 个点的带权树问有多少个无序点对 (u, v) 满足 u 到 v 的树上距离不超过给定的 k。这里的距离是唯一路径上边权之和不是边数。输入是多组数据每组第一行给 n 和 k后面跟 n-1 行边每组以0 0结尾。n 的规模在 10000 上下边权是小于 1001 的正整数。我第一次看这题的反应是这不就 n² 枚举一下然后看到 n 的范围就沉默了。这道题真正卡人的地方不在题意而在于它逼你放弃逐对枚举这个最自然的想法转而去思考如何把树上路径问题切成规模不断减半的子问题。这篇文章我打算从题意、思路、代码、调错四个层面完整过一遍适合那些会写 DFS、会存邻接表但一遇到树上统计就不知道从哪儿下手的朋友。1.1 题意与约束一句话版本再精确一点描述树上有 n 个节点节点编号从 1 到 n任意两点之间有且仅有一条简单路径。路径长度定义为这条路径上所有边权的和。要求统计出所有满足dist(u, v) k的顶点对数量注意 (u, v) 和 (v, u) 算同一对且 u 和 v 必须是不同的点。约束条件决定了算法选择的方向n 最多一万边权最大一千也就是说树上最远的两个点距离大概在一千万量级。这个数值很关键——它意味着任何以距离为下标的数组比如桶计数都会直接爆内存你只能按点数去设计复杂度不能按距离去设计复杂度。很多人第一次做这题会本能地想开一个dp[u][d]数组结果发现第二维根本开不下这就是踩的第一个坑。提示判断一道题能不能用按距离开数组的做法先算一下最大距离乘上点数是不是超过了一亿超过了就基本没戏。1.2 暴力解的复杂度账本最直接的暴力是从每个点出发做一次 DFS遍历整棵树求所有距离然后统计不超过 k 的点对。每一趟 DFS 是 O(n)一共 n 个起点总复杂度 O(n²)。当 n 等于 10000 时n² 是一亿次操作量级加上每组数据都要重来一次多组数据叠起来就是几亿甚至几十亿次基本操作。在常规的在线判题环境里C 每秒大概能跑一到三次一亿次简单操作而这个一亿里还包含大量的递归调用、数组访问和条件判断实际常数远不止 1。所以哪怕是最快的机器O(n²) 也一定超时。更麻烦的是这题的测试数据往往不是单组而是十几组极限数据连着来暴力的总代价还要再乘上组数。我实测过一版纯暴力本地跑 n10000 的单组大约要 0.6 秒看着还行但判题机上多组数据一叠加直接给 TLE。所以这题的暴力只能用来对拍验证正确性不能当作正式方案。1.3 为什么这题能进男人八题这题的难点其实不在代码量而在于它要求你同时掌握三件事第一树的重心这个概念知道为什么选中点之后子树规模能减半第二容斥的思想知道为什么统计完之后要减掉同一棵子树内部的那部分第三排序加双指针这个经典统计技巧知道怎么在一堆距离里线性数出满足和不超过 k 的点对数。这三件事单拿出来都不难但第一次要在一道题里同时用上很多人就会卡在容斥为什么减这一步。我当时就是把ans count(u, 0)写对了却漏了ans - count(v, w)样例过了交上去 WA。后来才想明白从重心往下的那一次统计把两点都在同一棵子树里的路径也算进去了而这些路径根本没经过重心是重复计数。2. 点分治的思路拆解从暴力枚举到按重心分而治之点分治这个名字听起来唬人本质其实很朴素找一个点把树拆成若干块让经过这个点的路径在这一层被统计完不经过这个点的路径递归到子块里继续统计。这么做的关键在于每一层统计的路径数量是经过当前分治中心的那些而剩下的递归到更小的块里块的规模按几何级数缩小所以总层数是 O(log n) 量级。理解这个框架之后剩下的所有细节都是怎么选点和怎么统计。选点的答案是重心统计的方法是排序加双指针再配容斥。下面我把每一步为什么这么做拆开讲。2.1 树上路径的两种基本情况对任意一棵正在处理的子树来说树上的路径只有两类一类是经过某个指定点 u 的另一类是完全落在 u 的某一棵子树里的。在图上看如果以 u 为根把树拎起来那么任何一条路径要么横跨了两个不同的子树必然经过 u要么整个待在同一个子树里必然不经过 u。这个二分法是整个算法的地基。因为你一旦选定 u 作为当前层的分治中心第一类路径就能在 O(size log size) 的时间里一次性全部数出来不需要对每条路径单独求距离。第二类路径则原封不动地交给递归去处理——把每棵子树当成一棵独立的小树重复同样的操作。所以整个算法就是处理经过我的递归处理不经过我的不断往下拆直到子树只剩一个点为止。这种每层只处理跨过分界点的部分的思路在后面做动态点分治、树上路径第 k 大之类的问题时还会反复出现值得在这里一次搞明白。2.2 为什么选重心而不是别的点既然任意选一个点都能拆为什么非得找重心因为重心的定义保证了去掉它之后剩余连通块的最大规模不超过当前规模的一半。这个性质直接决定了递归的深度如果每次都砍掉一半最多砍 log n 层就到底了总复杂度才是 O(n log² n)如果随便选点极端情况下树退化成一条链你在链头砍一刀剩下的还是 n-1 个点递归深度直接变成 n复杂度瞬间退化成 O(n²)。重心的严格定义是使得删掉该点后剩余各连通块中最大块的大小最小的那个点。等价地说最大的那部分越小越好。求解的方法是一次 DFS对每个节点 u先算出它作为根的每棵子树大小 sz[v]再算一下上方部分的大小tot - sz[u]tot 是当前连通块总点数两者取最大值就是删掉 u 之后的最大块。在所有节点里取这个值最小的那个就是重心。注意重心可能不止一个。当某个节点的最大块大小恰好等于一半时可能会同时存在两个重心随便取一个都能保证对数级的深度不用特别处理。2.3 容斥去重那一步减法到底减了什么这是点分治最容易写错的一步。以 u 为分治中心统计时我们是这样做的把 u 到它整个连通块内每个点的距离全部收集起来包括 u 自己距离为 0然后在这个距离集合里数出所有和不超过 k 的点对。问题来了这个集合里包含了大量两点位于 u 的同一棵子树的组合。比如 u 有两个儿子 v1、v2v1 下面有两个点 a、b那么 a 和 b 之间的路径根本不会经过 u它俩的距离在集合里的表现是 dep[a] dep[b]这里的 dep 都是从 u 出发的距离而这个和显然不是 a 到 b 的真实距离。如果不减掉这些假路径就会被错误计入答案会偏大。处理办法就是容斥对每一棵子树 v把v 子树内部点两两之间按从 u 出发算出的距离和统计出来从答案里减掉。注意减的时候v 自己也要作为距离为w(u,v)的点参与统计。这样做的效果是所有两点同属一棵子树的假组合被精确地消掉了剩下留在答案里的恰好就是真正经过 u 的路径。我用一个更直白的说法帮你记加法加的是以 u 为根的整棵树减法减的是每一棵子树的内部。先整体加一遍再把每棵子树的内部单独加一遍然后减掉等于什么都没加、又全都加了一遍——这是容斥最经典的写法。2.4 calc 内部为什么可以排序加双指针统计一对数的和不超过 k这类问题如果对每一对都判断一次是 O(m²)m 是收集到的距离个数。但排序之后就可以线性统计把距离数组从小到大排好用两个指针 l 和 r 分别指向两端。如果d[l] d[r] k说明 l 和从 l1 到 r 的所有点配对都成立直接加上r - l个然后 l 右移否则说明 d[r] 太大了r 左移。这个做法的正确性依赖于数组有序当d[l] d[r] k时任何比 d[l] 还大的数和 d[r] 相加只会更大所以 d[r] 可以和所有点一起被排除掉。反过来当d[l] d[r] k时d[l] 可以和所有比 d[r] 小的点配对。提示统计时循环条件必须是l r而不能是l r否则会把点对 (i, i) 自己配自己算进去。这一点在距离数组里包含 u 自己距离 0时特别容易出错。3. 手把手代码实现从框架到 AC前面讲的是为什么这一节讲怎么写。我按我平时写这题的顺序来先定全局数组再写三个辅助函数找重心、收集距离、统计最后拼分治主函数和输入输出。这套结构是我踩过几次坑之后固定下来的抄下来基本不用改。3.1 全局变量与数据结构设计存图用链式前向星因为它比vector邻接表在多组数据下更容易清空也不会有频繁 push_back 的开销。边数组开两倍节点数因为每条边要存正反两次。关键的几个数组vis[]标记某点是否已经作为重心被删掉后续递归不再进入它sz[]是子树大小mx[]是删掉该点后剩余最大块的大小dep[]是当前点到分治中心的距离buf[]用来临时收集距离。另外还需要全局的root当前连通块的重心和tot当前连通块的点数。数组名含义更新时机vis[u]该点是否已被当作重心分治过进入 divide(u) 时置真sz[u]以 u 为根的子树节点数每次 getRoot 遍历时重算mx[u]删除 u 后最大连通块大小每次 getRoot 遍历时重算dep[u]u 到当前分治中心的距离每次 getDep 时重算buf[]当前收集到的一批距离每次 count 前清空这里有个小细节值得一提mx[0]要设成一个极大的数比如 0x3f3f3f3f因为找重心时初始化root 0然后用mx[u] mx[root]来判断。如果 mx[0] 是 0那么所有节点都不满足条件root 会一直停在 0最后直接崩。3.2 找重心的实现细节找重心的 DFS 一次遍历就能同时算出 sz 和 mx。递归到子节点之后回溯更新sz[u] sz[v]同时用mx[u] max(mx[u], sz[v])记录最大子树。遍历完所有儿子之后别忘了还有上方那一坨tot - sz[u]也要参与最大值比较。比较同一棵树里所有节点的 mx 值取最小的那个当 root。注意这个比较是在 DFS 过程中顺手做的不需要第二遍遍历这也是为什么要把 root 设成全局变量——递归里没法方便地返回最小值和对应节点两个信息。注意如果某个邻接点 v 已经被 vis 标记过也就是它是更上层的重心必须直接跳过。这是保证每次处理的都是当前连通块而不是整棵树的关键。3.3 收集深度与统计收集距离的 DFS 从分治中心出发一路往下把dep[u]塞进 buf 数组。这里传入一个 base 参数作为起始距离是为了让容斥时复用同一个函数统计以 u 为中心时 base 传 0统计子树 v 的内部时base 传 u 到 v 的边权这样 v 自己的距离就是那条边的权值。统计函数 count 做的事很简单收集、排序、双指针。返回值就是这批距离里和不超过 k 的点对数。整个函数的复杂度是 O(m log m)m 是收集到的点数。3.4 分治主函数主函数 divide(u) 的流程是固定的四步把 u 标记为已访问加上count(u, 0)对每棵子树 v 减去count(v, w)然后以 v 所在连通块为新规模重新找重心并递归。第三步里有个容易忽略的点tot sz[v]必须在调用 getRoot 之前设置好因为 getRoot 要用 tot 来算上方部分的大小。而sz[v]此时还是上一轮 getRoot 算出来的值恰好就是 v 所在连通块的大小——这个恰好不是巧合而是因为上一轮遍历 u 时v 的子树正好就等于去掉 u 之后 v 的那一块。第四步里root 0也要重新置位因为要找的是新连通块的重心。3.5 完整可参考代码下面这份是我一直在用的版本C 编写直接在 POJ 上提交能过。多组数据用memset按 n 的大小清空避免整块清带来的额外开销。#include cstdio #include cstring #include algorithm using namespace std; const int MAXN 10005; const int MAXM MAXN 1; const int INF 0x3f3f3f3f; int n, K, ans; int head[MAXN], nxt[MAXM], to[MAXM], wgt[MAXM], ecnt; bool vis[MAXN]; // 是否已作为重心被分治过 int sz[MAXN]; // 子树大小 int mx[MAXN]; // 删掉自己后剩余部分的最大块 int dep[MAXN]; // 到分治中心的距离 int buf[MAXN], cnt; // 收集到的一批距离 int root, tot; void addEdge(int u, int v, int w) { to[ecnt] v; wgt[ecnt] w; nxt[ecnt] head[u]; head[u] ecnt; } // 在 u 所在连通块内找重心tot 为该连通块点数 void getRoot(int u, int fa) { sz[u] 1; mx[u] 0; for (int i head[u]; i; i nxt[i]) { int v to[i]; if (v fa || vis[v]) continue; getRoot(v, u); sz[u] sz[v]; if (sz[v] mx[u]) mx[u] sz[v]; } if (tot - sz[u] mx[u]) mx[u] tot - sz[u]; if (mx[u] mx[root]) root u; } // 收集 u 到其子树内所有点的距离 void getDep(int u, int fa, int d) { dep[u] d; buf[cnt] d; for (int i head[u]; i; i nxt[i]) { int v to[i]; if (v fa || vis[v]) continue; getDep(v, u, d wgt[i]); } } // 统计 buf 中两点距离之和 K 的点对数 int count(int u, int base) { cnt 0; getDep(u, 0, base); sort(buf 1, buf cnt 1); int l 1, r cnt, res 0; while (l r) { if (buf[l] buf[r] K) { res r - l; l; } else --r; } return res; } void divide(int u) { vis[u] true; ans count(u, 0); // 加上经过 u 的路径 for (int i head[u]; i; i nxt[i]) { int v to[i]; if (vis[v]) continue; ans - count(v, wgt[i]); // 容斥减掉同一子树内部的重复统计 tot sz[v]; root 0; getRoot(v, u); divide(root); } } int main() { while (scanf(%d%d, n, K) 2) { if (n 0 K 0) break; memset(head, 0, sizeof(int) * (n 1)); memset(vis, 0, sizeof(bool) * (n 1)); ecnt 0; ans 0; for (int i 1; i n; i) { int u, v, w; scanf(%d%d%d, u, v, w); addEdge(u, v, w); addEdge(v, u, w); } tot n; root 0; mx[0] INF; // 关键初始化 getRoot(1, 0); divide(root); printf(%d\n, ans); } return 0; }这段代码里有几个位置是看着可以省、实际不能省的。比如mx[0] INF放在循环外面只设一次也行但放在每组数据开头更安全count(v, wgt[i])里的wgt[i]不能写成 0写成 0 就等于把子树内部的统计变得毫无意义while (l r)不能改成。4. 复杂度分析与边界参数写完代码只是第一步能不能放心交上去还得看复杂度账算不算得过来以及各种边界情况会不会翻车。这一节把这两件事说清楚。4.1 为什么总复杂度是 O(n log² n)把每一层分开算。在某个连通块上getRoot 遍历整块一次是 O(size)getDep 收集所有点一次也是 O(size)排序的开销是 O(size log size)所以单层的总代价是 O(size log size)。关键在于所有层的 size 之和。因为每次选的都是重心每棵子树规模不超过当前的一半所以从根往下走每一层的 size 之和不超过 n。层数是 O(log n)。把这两者相乘就得到 O(n log² n)——那个额外的 log 来自每层的排序。对比一下暴力的 O(n²)n10000 时是一亿量级O(n log² n) 大约是 10000 × 13 × 13 ≈ 170 万量级。差了将近两个数量级这就是它能过的原因。至于排序还可以用基数排序把那个 log 干掉变成 O(n log n)但在这题的数据规模下完全没必要。方案复杂度n 10000 时的量级能否通过逐点 DFS 暴力O(n²)约 1 亿多组数据下 TLE树上按距离 DPO(nk)与 k 同阶超出数组上限无法实现点分治 排序O(n log² n)约 170 万稳定通过4.2 数组大小、递归深度与常数优化第一数组开多大。题目说 n 不超过 10000那么 MAXN 开 10005 就够。但如果你的模板要复用到别的题上建议直接开到 100005反正内存不吃紧。边数组记得开两倍反边很容易忘。第二递归深度。getRoot 和 getDep 的递归深度最坏等于当前连通块的规模n10000 时一万层递归在默认栈空间下是安全的大约几 MB。但如果把这份代码拿去跑 n10⁵ 的题就必须考虑手动扩栈或者改写成迭代版本。第三答案的数据类型。n10000 时最多有约 5000 万对点int够用。但如果你要把它当作通用模板建议直接上long long免得换题时忘了改导致溢出。第四清空数组的方式。多组数据下每次memset整个 MAXN 大小的数组会带来额外开销虽然这题数据量小看不出来但习惯上还是按实际 n 的大小来清。上面代码里我用sizeof(int) * (n 1)这种方式就是为了这个。注意memset清 bool 数组时用的是sizeof(bool)虽然通常是 1 字节但如果平台实现不同会有隐患稳妥起见可以直接写sizeof(vis)。5. 常见问题与排查实录这题我前前后后写废过好几版也在别人的代码里见过各种奇怪的错法。这里把最容易踩的几个坑整理成一张表再补充几条只有实际调过才知道的经验。5.1 典型错误速查表现象可能原因排查方向样例过提交 WA漏了容斥减法检查是否对每棵子树调用count(v, wgt[i])答案偏大且接近 n²双指针写成l r改成l r排除点对自配死循环 / 栈溢出重心找成了普通点检查mx[0]是否设为极大值第二组数据开始答案乱数组没清干净检查 vis、head、ecnt、ans 是否重置部分点 TLE递归时没跳过 vis[v]检查 getRoot、getDep 的跳过条件答案偏小距离数组少收了一个点检查 base 传参和 dep 赋值顺序5.2 我在调这题时踩过的坑第一个坑是容斥时把 base 传成 0。当时我的想法是子树内部统计嘛从 v 出发距离当然是 0结果答案比正确值大了不少。原因是从 v 出发算出来的距离和从 u 出发算出来的距离差了一个w(u,v)。如果两边都从自己出发算 0那同一棵子树里两个点按 u 为参考系的距离和就变了减掉的根本不是同一个东西。所以 base 必须传那条边的权值让 dep 的参考系保持一致。第二个坑是多组数据忘了重置 ecnt。链式前向星是靠ecnt递增来分配位置的如果不清零第二组数据会从上一组的尾部继续分配而 head 已经清空了导致新旧边混在一起。这个 bug 特别难查因为第一组数据永远是对的只有多组连测才会暴露。第三个坑是把tot的设置位置搞错。我一开始是在 getRoot 内部根据遍历结果自己算总点数结果发现每次算出来的都不对。正确做法是外层传进去初次调用传 n递归时传sz[v]。因为 getRoot 遍历的是当前连通块而它没法自己知道这个块的边界在哪儿——边界是由 vis 决定的靠遍历是数不出上方那一坨的。第四个坑和性能有关在 count 里用 vector 动态分配。我早期写过一个版本每次统计都新建一个 vector 存距离结果虽然复杂度对了但常数大得离谱勉强卡过。后来换成全局静态数组加计数器速度提升非常明显。这类临时缓冲最好都用全局数组复用别在热路径里做内存分配。最后分享一个调试技巧如果怀疑容斥写错了可以先把ans - count(v, wgt[i])注释掉看看答案是不是偏大如果怀疑重心写错了可以加一个断言检查每次找到的重心的 mx 值是否不超过tot / 2。这两个小改动能帮你快速定位问题出在统计环节还是分治环节。6. 从这题延展出去点分治还能怎么用把第一题吃透之后你会发现这套找重心、统计、容斥、递归的框架几乎可以原样搬到一大类问题上改变的只是中间那个 count 函数怎么数。最直接的一种变体是统计距离恰好等于 k 的点对把双指针里的小于等于改成等于再配合去重即可。再复杂一点是求树上长度不超过 k 的路径条数中长度最小的若干条这时候可以把排序换成二分答案外层套一层二分复杂度变成 O(n log³ n)。另一个常见方向是求树上路径的第 k 大或者满足某种条件的路径计数前者需要配合可持久化结构后者往往把排序统计换成一个树状数组或前缀和思路仍然是经过中心的路径在这一层处理完。还有个很实用的延展是点分治 树状数组的动态版本也就是常说的动态点分治。它把分治过程中每个重心到其上级重心的距离预先存下来之后支持单点修改和在线查询路径信息。这类题难度比 1741 高一个档次但如果 1741 写得足够熟练理解起来会顺畅很多。我自己的经验是点分治真正的门槛不在代码而在敢不敢相信那个容斥减法。第一次写的时候看到ans count(u, 0)和ans - count(v, w)这两行并排放着心里总觉得别扭——加了一遍又减一遍图什么呢。等你把一棵三节点的小树在纸上画出来把每一对被统计和被减掉的次数标出来一下子就会明白加法负责覆盖所有候选减法负责剔除假路径两者配合才恰好剩下真正跨过分治中心的那部分。这个理解一旦建立后面无论遇到什么变体你都知道该在哪一层动手、该减去什么。