CSP-S 2025 第一轮 第10题：在一棵以结点 1 为根的树中，结点 12 和结点 18 的最近公共祖先（LCA）

题目

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

选项

• A. $LCA(12, 4) = 4$
• B. $LCA(18, 4) = 4$
• C. $LCA(12, 18, 4) = 4$
• D. $LCA(12, 1) = 4$

答案

D

题解

答案是 D。

已知 \(LCA(12,18)=4\)，说明结点 \(4\) 是 \(12\) 和 \(18\) 的共同祖先。注意：一个结点也算它自己的祖先。

• A：\(4\) 是 \(12\) 的祖先，因此 \(LCA(12,4)=4\)，成立。
• B：同理，\(LCA(18,4)=4\)，成立。
• C：\(4\) 是 \(12、18、4\) 的最近公共祖先，成立。
• D：结点 \(1\) 是根，任意结点与根的最近公共祖先都是根，所以 \(LCA(12,1)=1\)，不可能是 \(4\)。