最近公共祖先 (图论)

在图论和计算机科学中，最近公共祖先（）是指在一个树或者有向无环图中同时拥有和作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果是的后代，那么就是和的最近公共祖先。

最近公共祖先是两个节点所有公共祖先中离根节点最远的，计算最近公共祖先和根节点的长度往往是有用的。比如为了计算树中两个节点v和w之间的距离，可以使用以下方法：分别计算由v到根节点和w到根节点的距离，两者之和减去最近公共祖先到根节点的距离的两倍即可得到v到w的距离。