CSP-S 提高级 · CSP 2023 提高级第一轮 第 12 题

在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心？

这题考树的重心数量规律。拿到题先想：重心若有两个，必相邻且平分节点；奇数节点无法平分，故唯一。7是奇数，直接锁定C。

容易凭直觉选4（觉得节点少就唯一）或8（觉得偶数才不唯一）。需理解核心规律：奇数个节点→唯一重心；偶数个节点→可能有1个或2个。比如4个节点的链1-2-3-4，删2或3最大子树都是2，故有两个重心；8个节点同理，中间两个相邻节点都能平分。记住这个反例逻辑，就不会被数字大小误导。

考察知识点： 树形结构 — 树的重心

重心数量定理： 一棵树要么有1个重心，要么有2个重心。如果有2个重心，它们一定相邻，且此时树被分成两个大小为 n/2 的部分。

推论： 当 n 为奇数时，不可能均分成两个整数的 n/2，所以一定有且仅有1个重心。

验证各选项：

• 节点数4（偶数）：可能2个。反例：链1-2-3-4，删2或3最大子树大小均为2，故有两个重心。
• 节点数6（偶数）：可能2个。反例：链1-2-3-4-5-6，删3或4最大子树大小均为3，故有两个重心。
• 节点数7（奇数）：一定1个。奇数个节点无法平分，故唯一。
• 节点数8（偶数）：可能2个。反例：链1-2-...-8，删4或5最大子树大小均为4，故有两个重心。

如何求树的重心？ 1. 任选一个节点为根，DFS算出每棵子树的大小。 2. 对每个节点，计算删它后的最大子树大小 = max(最大子树大小, n - 当前子树大小)。 3. 取这个值最小的节点即为重心。

技巧： 重心相关的结论题，记住“奇数节点 → 唯一重心”这个推断即可秒杀。