CSP-S 提高级 · CSP 2026 提高级第一轮 第 10 题

【单选】无根树含 9 个结点（编号为 1—9），边集为 {(1,2),(1,3),(2,4),(2,5),(3,6),(6,7),(7,8),(5,9)}。该树的直径（以边数计）与重心分别是（ ）。

直径 = 树上最远两点间的边数，Dijkstra 式"两遍搜索"或手数最长路径即可；重心 = 删掉它之后最大连通块最小的那个点。先画出这棵树，再找最长链和平衡点。

把直径数成"结点数"（7 个点 → 错答 8 或 6）；重心误判为 2（因为 2 的子树看起来也很大），但删掉 1 后的最大块是 4 个，删掉 2 后是 5 个，故重心是 1。

解析

本题考查树的直径与重心，必须先画出这棵树。

树的形状

边集 {(1,2), (1,3), (2,4), (2,5), (3,6), (6,7), (7,8), (5,9)}，共 8 条边、9 个结点：

        4
        |
   1 - 2 - 5 - 9
   |
   3 - 6 - 7 - 8

直径（最远两点间的边数）

从 4 出发：4 → 2 → 1 → 3 → 6 → 7 → 8，共 6 条边； 从 9 出发：9 → 5 → 2 → 1 → 3 → 6 → 7 → 8，共 7 条边； 从 8 出发：8 → 7 → 6 → 3 → 1 → 2 → 4（6 条）或 → 5 → 9（7 条）。

最长的是 9 到 8（也等价于 9 到 7 再延伸），经过边数 = 7，即

直径 = 7（按边计）

（若按"结点数"计则是 8 个点，题面明确"以边数计"，务必看清。）

重心（删去后最大连通块最小的结点）

对每个候选点，删掉它后看最大的那块有多大：

最大块最小的结点是 1（最大块 4 ≤ ⌈9/2⌉ = 5，恰好也是直径路径的中点）。

所以：直径 7，重心为结点 1 → 选 D。

其他选项为什么错

• A. 直径 6、重心 3：直径数成了 4 到 8 那条链；重心把 3 当成中心；
• B. 直径 7、重心 2：重心错——删 2 后最大块是 {1,3,6,7,8} 共 5 个，比删 1 的 4 个大；
• C. 直径 8、重心 1：直径按"结点数"数成 8。

记忆点

• 直径求法：任取一点做 BFS/DFS 找到最远点 u，再从 u 做一遍找到最远点 v，则 dist(u,v) 就是直径（两遍搜索法）；
• 重心判别：删掉它以后每棵子树（含"向上的那部分"）大小都 ≤ n/2；本题 1 满足（两棵子树各 4 ≤ 4.5）；
• 直径与重心都在"最长路径的中点"附近，做题时先画树再数最稳。