LCA介绍
和它的全称一样,lca(LowestCommonAncestorLowest Common AncestorLowestCommonAncestor)目的就是任意两个点最近的公共祖先在哪
性质 (或许你不需要记这个)
From OI-wiki
为了方便,我们记某点集 S={v1,v2,...,vn}S = \left\{ v_1,v_2,...,v_n \right\}S={v1,v2,...,vn} 的最近公共祖先为 LCA(v1,v2,...,vn)LCA(v_1,v_2,...,v_n)LCA(v1,v2,...,vn) 或 LCA(S)LCA(S)LCA(S)
LCA({u})=uLCA(\left\{u\right\}) = uLCA({u})=u ;
若 uuu 是 vvv 的祖先,当且仅当 LCA(u,v)=uLCA(u, v) = uLCA(u,v)=u ;
如果 uuu 不为 vvv 的祖先,并且 vvv 不为 uuu 的祖先,那么 u,vu, vu,v 分别处于 LCA(u,v)LCA(u, v)LCA(u,v) 的两 ...