CF686D 这道题我最早是在训练树上结构时遇见的。当时第一反应是“又是树的重心模板题”但仔细拆完发现它比单纯求一次重心要刁钻得多题目要求把树上每个节点各自子树的重心全部预处理好然后面对 q 次询问做到 O(1) 回答。n 和 q 都能到 3e5如果每次询问单独去搜索重心最坏情况就是 O(nq)直接原地爆炸。正解的关键在于理解树的重心怎么在父子节点之间“交接棒”。这篇内容我就围绕 CF686D 把树的重心性质、递推思路和完整实现一次讲透适合正在练树形 DP、点分治或者想提高图论建模能力的读者。1. 题目到底在问什么重心的定义和场景1.1 重心的两种等价理解树的重心在竞赛里有两种说法大多数人背下来的是“删掉这个点后剩下的最大连通块最小”。这个定义虽然严谨但做题时用起来并不顺手因为“最大连通块最小”这句话在代码里不太好直接判断。更常用的判断方式是它的等价形式以重心为根时所有子树的大小都不超过整棵树大小的一半。为什么等价你试想一下把一个点当作根它的每个邻居往下扩出去的部分就是删掉这个点之后的一个连通块反过来删掉这个点形成的每一块在以它为根时也正好对应一棵子树。所以“最大连通块不超过 n/2”和“所有子树都不超过 n/2”是一回事。判断的时候就方便多了。给定一棵大小为 sz 的树和一个候选点 x我只要看下面两个条件是否同时满足x 的每个儿子子树大小 ≤ sz/2父侧那块的大小也就是整个树去掉以 x 为根的这棵子树后剩下的节点数也要 ≤ sz/2如果都满足x 就是重心。1.2 为什么 CF686D 不是“求一次重心”那么简单CF686D 的题意可以概括成给一棵 n 个节点的有根树节点 1 是根接下来给 q 个询问每次给定一个节点 v要求输出以 v 为根的子树也就是 v 和它的所有后代组成的连通块的重心编号。需要注意这里的“子树”不是通常无根树里的任意子树而是以 1 为根后每个节点向下覆盖的那个子树。输入保证 p_i i也就是说每个节点的父节点编号一定比自身小树本身已经以一种“自顶向下”的顺序给你了。如果只问整棵树的重心一条从根往下搜索的链就能搞定判断每个候选点是否满足所有子树大小的限制即可。但这里要对每个节点都求一遍一个简单粗暴的暴力做法是对每个询问 v收集 v 的子树然后枚举里面的每个点判断是否为重心单次 O(子树大小)总复杂度 O(nq)。n 和 q 同时到 3e5 时这显然不可行。所以这道题真正考察的是如何一次性把所有子树的重心全部递推出来。1.3 树的重心在竞赛里的常见出场位置如果只把重心当成一个孤立的知识点学完很快就会忘。它其实经常出现在这些题目里点分治每次找当前树的重心作为分治中心保证递归层数是 O(log n)这是树的“平衡分割”思想。动态树问题两棵树合并时求新树重心重心一定在原来两个重心的路径上这个性质经常配合并查集使用。换根 DP求“删掉哪个点后最大连通块最小”这类问题本质就是重心。CF686D 属于“静态预处理所有子树重心”的典型代表吃透这道题对理解后续点分治里的 get_root 函数非常有帮助。2. 核心观察为什么答案要从重儿子手里接2.1 重心只会藏在“超过一半的那棵子树”里假设当前要处理的点是 u它的子树大小为 sz[u]。我们先不管 u 具体是几号节点只看它维护的这棵子树内部。如果 u 的所有儿子子树都不超过 sz[u]/2那 u 本身就已经是重心了直接让 ans[u] u 就行。可如果存在某个儿子 vsiz[v] sz[u]/2u 就不可能是重心重心必须到 v 这棵子树里面去找。为什么必然跑到 v 里面反证法如果重心 x 在 v 子树之外删除 x 之后原来 v 这整棵子树仍然是一个完整的连通块这个块大小是 siz[v]它已经严格超过 sz[u]/2 了。这违反了“删掉重心后最大连通块 ≤ 整棵树一半”的核心条件矛盾。所以只要存在一个“过半儿子”重心就一定在这个儿子内部。这个结论看似简单却是整道题的杠杆点。它把我们搜索的范围一下子缩小到了唯一一棵大子树里。2.2 “从重儿子的重心往上爬”是怎么想出来的现在我们知道 u 的重心藏在重儿子 heavy 的子树里但到底怎么定位一个朴素想法是从 heavy 往下走进重子树再进重子树一直走到叶子然后回溯找到重心。这在链上会退化得非常严重单次查询就能走到叶子整体复杂度不能接受。换一个视角heavy 子树本身也有一棵自己的子树结构而它的重心我们已经递归算出来了记作 ans[heavy]。那么 u 的重心会不会和 ans[heavy] 有关系答案是肯定的它就在从 ans[heavy] 往父节点爬到 u 的这一条路径上。这个结论的证明依然靠重心条件。由于 ans[heavy] 是 heavy 子树的重心所以在它下面的每一棵子树大小都不会超过 siz[heavy]/2更不会超过 sz[u]/2。唯一可能超过 sz[u]/2 的是 ans[heavy] 往上到 u 的那一侧也就是“父侧块”。也就是说把 ans[heavy] 放到整棵 u 子树里看它能不能当重心只取决于一个数siz[u] - siz[ans[heavy]]这表示删掉 ans[heavy] 后除它自身子树以外包含 u、heavy 祖先链以及 u 其他分支的那一大块有多大。如果这个数超过 sz[u]/2ans[heavy] 就不合法得往上移一步再次检查新的父侧块大小。每次上移siz[ans] 都会变大父侧块就会变小循环一定会停。2.3 两个重心的情况怎么处理重心最多有两个而且如果有两个它们一定相邻。这个性质在做题时经常被忽略但它对 while 循环的终止条件很重要。什么时候会出现两个重心假设一条边连接 x 和 y如果以 x 为根时y 那一侧恰好是 sz/2同时 y 的其余子树都小于等于 sz/2那么 y 也是重心。反过来同样成立。代码里用 while 循环往上走循环条件是父侧块严格大于 sz[u]/2。也就是说当父侧块等于 sz[u]/2 时我们停下来。这个时刻选中的点是离重儿子更近的那个重心。两个重心相邻所以从树结构上讲选哪个都合法题目通常用 SPJ 判断只需要输出任意一个重心即可。2.4 上移次数为什么可以接受有人会担心如果构造一条长链每个节点都从重儿子的重心一路往上爬会不会总复杂度变成 O(n^2)链这种极端情况其实并不可怕。你可以把上移过程理解成候选点每往上移动一次它所在的那一侧子树大小至少会变大到一个新的量级整条路径经过的节点数不会超过 O(log n)。更宽松地说即使单次上移可能是 O(log n) 或者接近 O(logn) 的级别总复杂度也在 O(n log n) 以内对于 n3e5 的规模完全能跑过。如果还想更稳可以用倍增把单次查询压到 O(log n)但 CF686D 这道题普通 while 写法在标准数据下表现已经足够好主要难度在于理解为什么可以这样递推。3. 递推框架与 C 实现3.1 需要维护的状态正解是一遍后序 DFS自底向上处理每个节点。需要三个数组siz[u]以 1 为根时u 的子树大小。ans[u]以 u 为根的子树的重心编号这是最终要输出的答案。heavy[u]u 的儿子里siz 最大的那个儿子也就是重儿子。后序 DFS 的意思是先递归处理所有儿子再处理当前节点。这样当处理 u 时所有儿子的 siz 和 ans 都已经算好了。伪代码思路初始化 siz[u] 1。遍历每个儿子 v递归处理然后 siz[u] siz[v]。找出重儿子 heavy。如果没有儿子说明 u 是叶子ans[u] u。否则 ans[u] 先赋值为 ans[heavy]然后不断检查“父侧块”是否超过 sz[u]/2如果超过就把 ans[u] 上移直到满足条件。while 循环的判断条件要重点说明while ((siz[u] - siz[ans[u]]) * 2 siz[u]) ans[u] fa[ans[u]];这里的 siz[u] - siz[ans[u]] 就是删除候选点后上方那一块的大小。注意必须乘 2 再和 siz[u] 比较避免浮点数误差。3.2 手推一棵 8 个节点的树光看公式容易抽象我拿一棵具体的树走一遍完整流程。设树的父子关系如下1 的儿子是 2、32 的儿子是 4、55 的儿子是 6、7、8整棵树共 8 个节点。先看叶子4、6、7、8、3它们的子树大小都是 1也没有儿子所以 ans 都是自身。接着处理节点 5。5 的子树包括 {5,6,7,8}大小 siz[5] 4。它的三个儿子都是叶子重儿子随便取一个就取 6。ans[5] 先设为 ans[6] 6。检查上方块siz[5] - siz[6] 4 - 1 33 * 2 6 4说明 6 不行往上移动到父节点 5。此时上方块为 4 - 4 00 * 2 4 不成立停。所以 ans[5] 5。再处理节点 2。2 的子树包括 {2,4,5,6,7,8}大小 siz[2] 6。重儿子是 5。ans[2] 先设为 ans[5] 5。检查上方块siz[2] - siz[5] 6 - 4 22 * 2 4 6 不成立停。ans[2] 5。这符合直觉删掉 5 后剩下的是 {2,4}大小 2不超过 3。最后处理根 1。整棵树大小 siz[1] 8重儿子是 2。ans[1] 先设为 ans[2] 5。检查上方块siz[1] - siz[5] 8 - 4 44 * 2 8 8 不成立停。所以整棵树重心是 5。验证一下删掉 5 后连通块分别是 {6}、{7}、{8}、{2,4,1,3}最大那块是 4刚好等于 8/2合法。这个过程能很清楚地看到节点 1、2、5 其实共享了同一个候选重心 5只是检查的上方块大小不同。3.3 递归版完整代码#include bits/stdc.h using namespace std; const int MAXN 300005; int n, q; int fa[MAXN], siz[MAXN], ans[MAXN]; vectorint child[MAXN]; void dfs(int u) { siz[u] 1; int heavy 0; for (int v : child[u]) { dfs(v); siz[u] siz[v]; if (heavy 0 || siz[v] siz[heavy]) { heavy v; } } if (heavy 0) { ans[u] u; return; } ans[u] ans[heavy]; while ((siz[u] - siz[ans[u]]) * 2 siz[u]) { ans[u] fa[ans[u]]; } } int main() { scanf(%d%d, n, q); for (int i 2; i n; i) { scanf(%d, fa[i]); child[fa[i]].push_back(i); } dfs(1); while (q--) { int v; scanf(%d, v); printf(%d\n, ans[v]); } return 0; }这段代码在 n3e5 的 C 环境下通常能稳定通过。注意 vector 的访问是 O(1)整体空间也符合要求。3.4 非递归写法利用 p_i i 避免爆栈有些 OJ 的栈空间比较小递归 dfs 在链形数据下可能爆栈。这道题的输入有一个特殊性质父节点编号一定小于子节点编号。这意味着我们可以不建递归栈直接从 n 到 1 倒序递推。先处理 siz 和 heavyfor (int i 1; i n; i) siz[i] 1; for (int i n; i 2; --i) { siz[fa[i]] siz[i]; // 这里需要知道每个父节点的重儿子 }重儿子可以在累加的过程中更新for (int i 1; i n; i) siz[i] 1; for (int i n; i 2; --i) { int f fa[i]; siz[f] siz[i]; if (heavy[f] 0 || siz[i] siz[heavy[f]]) { heavy[f] i; } }然后从 n 到 1 倒序计算 ansfor (int i n; i 1; --i) { if (heavy[i] 0) { ans[i] i; continue; } ans[i] ans[heavy[i]]; while ((siz[i] - siz[ans[i]]) * 2 siz[i]) { ans[i] fa[ans[i]]; } }因为子节点编号大于父节点倒序循环保证了处理到 i 时i 的所有后代节点都已经处理完毕ans[heavy[i]] 必然已经算好。这个技巧在不少树的递推题里都能用是一个值得记下来的常规套路。4. 边界情况、复杂度与排错心得4.1 边界用例链、星形和两个重心写这类题最容易出问题的不是主逻辑而是各种边界数据。我习惯写完代码后先脑补几类特殊形状的树。第一类是链。比如 1-2-3-4这棵树如果只求根节点 1 的重心答案是 2 或 3 都可以。拿递归版跑一遍最终 ans[1] 会落在 3因为它继承的是重儿子子树里重心再往上跳的结果两个重心选哪个由 while 的严格不等号决定。输出 3 是完全合法的。第二类是星形。节点 1 连接其他所有节点每个叶子子树大小都是 1。对根 1 来说最大儿子子树 1 不大于整棵 n/2只要 n≥3所以 ans[1] 1这是对的。对每个叶子ans[leaf] leaf也正确。第三类是大小为偶数的完全平分结构。例如两个节点 1-2以 1 为根的子树大小为 2删掉 1 后最大块为 1不大于 1所以 1 是重心同理 2 也是重心。我们的 while 条件里如果 ans 先落在 2检查上方块 2-111*22 2 不成立因此输出 2。同样合法。4.2 常见错误和调试清单我在对拍时踩过几次坑整理成清单供参考。忘记给 siz[u] 初始化为 1。初始化为 0 后所有子树大小都会少算当前节点后序一切贪心判断全乱。重儿子更新时只取了第一个儿子。要记录最大 siz 的那个儿子否则答案可能跳到错误的候选点。while 循环里写成了 (siz[u] - siz[ans[u]]) siz[u] / 2。这个写法在 siz[u] 是奇数时可能有精度问题最好统一乘 2 比较避免整数除法带来的误差。把 while 里的严格大于写成了大于等于。这样遇到两个重心时会强制往上多走一步走到另一个重心。这个其实不致命因为两个重心都合法但如果你期望的答案是“靠近叶子那个”就得注意保持一致。在递归版里遍历所有邻接点而不是只遍历儿子。如果存的是无向边需要判断 v ! fa[u]否则会反复横跳。4.3 对拍验证小技巧如果不确定自己写的重心是否正确最快的办法是写一个暴力版本对拍。暴力思路很简单对每个节点 u收集它的子树节点集合然后枚举集合里的每个点 x检查以 x 为根时所有邻居方向上的连通块大小是否都不超过 siz[u]/2。复杂度 O(n^2) 没问题只用来跑小数据。然后随机生成 n200 以内的树输入固定根为 1比较暴力版和递推版的每个 ans 是否一致。因为树的重心可能有两个比较时要允许两种答案都算对。更简单的方法是直接写一个 check 函数传入节点 u 和候选点 x验证 x 是否为 u 子树的重心然后对递推版的输出逐一 check。我实际用这个方式抓到过一个问题有一版代码在处理“根节点的轻儿子是重儿子”时没有重新比较导致候选点落在了轻儿子的子树里对拍一跑就暴露了。4.4 思路可以怎么扩展CF686D 的递推本质是当前节点的答案可以从重儿子的答案向上爬得到。这个模型不仅适用于“子树重心”在很多父子状态递推的树形结构题里都能套。比如点分治里每次分治时都要找当前连通块的重心。如果用递归对每个连通块重新搜索代码会很绕而如果先把整棵树的 siz 预处理出来再利用父侧块大小的判断就可以在“候选点”之间移动避免每次从零开始扫全树。再比如换根求“每个节点作为根时的重心”那是另一个方向的题目思路是重心只会沿着原重心的方向移动本质上也是移动指针而不是暴力重算。把 CF686D 的“父侧块大小判断法”吃透这类移动思想自然就通了。我在实际训练中最大的体会是树的重心题往往不是难在计算而是难在找到一个好的“起始候选点”。只要想到从重儿子的重心出发再往上微调复杂度就会骤然降下来。遇到重心的题目先画一棵小树标出每个子树大小再手动往父方向走两步你就知道 while 条件为什么必须那样写了。