Content #
u 和 v 的公共祖先指一个节点既是 u 的祖先，又是 v 的祖先。u 和 v 的最近公共祖先指距离 u 和 v 最近的公共祖先。若 v 是 u 的祖先，则 u 和 v 的最近公共祖先是 v。
树上任意两点之间的距离(用 LCA 求解):
dist[u]+dist[v]-2×dist[lca]。
求解LCA的算法 #
暴力搜索法 #
- 向上标记法
从 u 向上一直到根节点，标记所有经过的节点；若 v 已被标记，则 v 节点为 LCA(u, v)；否则 v 也向上走，第 1 次遇到已标记的节点时，该节点为 LCA(u, v)。
- 同步前进法
将 u、v 中较深的节点向上走到和深度较浅的节点同一深度，然后两个点一起向上走，直到走到同一个节点，该节点就是 u、v 的最近公共祖先，记作 LCA(u,v)。若较深的节点 u 到达 v 的同一深度时，那个节点正好是 v，则 v 节点为 LCA(u, v)。
树上倍增法 #
From #
《算法训练营进阶篇》 陈小玉