LCA
基本概念
对于一个有根树，如果点 \(z\) 既是点 \(x\) 的祖先，又是点 \(y\) 的祖先，则说点 \(z\) 是 \(x\) 和 \(y\) 的公共祖先。每对点的所有公共祖先里，深度最大的那个点被称作这两个或多个点的最近公共祖先（lca）。
lca 有很多优秀的性质，例如经过 lca 的路径是两点间的最近路径等。
（未完待续）
【图论】最近公共祖先 学习笔记
发布时间 2023-10-14 19:15:58作者: 蒟蒻OIer-zaochen
对于一个有根树，如果点 \(z\) 既是点 \(x\) 的祖先，又是点 \(y\) 的祖先，则说点 \(z\) 是 \(x\) 和 \(y\) 的公共祖先。每对点的所有公共祖先里，深度最大的那个点被称作这两个或多个点的最近公共祖先（lca）。
lca 有很多优秀的性质，例如经过 lca 的路径是两点间的最近路径等。
（未完待续）