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

在一棵以结点 $1$ 为根的树中，结点 $12$ 和结点 $18$ 的最近公共祖先（LCA）是结点 $4$。那么下列哪个结点的 LCA 组合是不可能出现的？

这题考树的基本性质和LCA定义。拿到题先抓住根节点1的特殊地位——任何节点与根的LCA必为根。再看已知条件LCA(12,18)=4，说明4是12和18的公共祖先，且是最深的。从这两个核心点出发，逐个检验选项就能秒杀。

很多学生看到LCA(12,18)=4就以为4是整棵树的根，或者想当然认为4能作为其他组合的LCA。其实根节点1才是唯一的根，LCA(任意节点,1)永远等于1，不可能等于4。另外，选项C涉及三元LCA，容易让人纠结顺序，其实LCA(a,b,c)=LCA(LCA(a,b),c)，只要前两个的LCA是4，再和4求LCA自然还是4。

考察知识点

图论 — LCA（最近公共祖先）

概念定义

• LCA（Least Common Ancestor）：在树中，两个节点的最近公共祖先，即同时是两节点祖先且深度最大的节点。
• 根节点性质：根节点是所有节点的祖先。任何节点与根节点的LCA都是根节点。
• 三元LCA：$LCA(a,b,c) = LCA(LCA(a,b), c)$。

命题视角

命题人特意给了一个非根节点4作为LCA(12,18)的结果，这是为了诱导学生忽略根节点1的绝对地位。同时加入三元LCA选项，考察对结合律的理解。这种组合式提问是近年CSP提高级的经典套路：用看似复杂的组合掩盖最基础的定义。

逐步推导

已知 LCA(12,18) = 4，所以 4 在 12 和 18 的祖先路径上，且是最深的公共祖先。这意味着 4 是 12 的祖先，也是 18 的祖先。

逐一分析：

• A. LCA(12,4)=4 — 可以成立！因为 4 是 12 的祖先，它们俩的最近公共祖先就是 4 自己。
• B. LCA(18,4)=4 — 同理，4 是 18 的祖先，LCA 自然是 4。
• C. LCA(12,18,4)=4 — 按定义 $LCA(12,18,4) = LCA(LCA(12,18), 4) = LCA(4,4) = 4$，完全成立。
• D. LCA(12,1)=4 — 这里踩了大坑！1 是整棵树的根节点。根据 LCA 的基本性质，任何节点与根节点的 LCA 一定等于根节点。所以 LCA(12,1) 必然是 1，绝不可能等于 4。

避坑指南

LCA(任意节点, 根节点) = 根节点，这是一个基本性质，必须刻在脑子里。节点 1 是根，任何节点与根节点的 LCA 一定是 1。选项 D 把 4 当成 12 和 1 的 LCA，违背了这个铁律。

考频与趋势

LCA 考点在 CSP 提高级中属于高频核心内容。根据真实数据：题库共考过 2 题，覆盖 1 个考试级别（2021-2025）；逐年分布：2021年1题、2025年1题；分赛事：CSP 提高级2题。这说明该知识点在近三年保持了稳定的考查频率。

预测

基于现有数据，LCA 在 CSP 提高级中的考频呈现偶数年与奇数年交替出现的趋势（2021年1题，2025年1题）。考虑到信息学竞赛对树形结构算法的持续重视，预计未来几年该考点仍会高频出现，且命题形式可能会更加灵活，例如结合树的重心、直径等概念进行综合考查。暂无足够依据预测具体年份的题量变化。