MorsLin 的博客
前事不忘,后事之师
题解 P3379 [[模板]最近公共祖先(LCA)]
LCA(Least Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先.  -  -  - 来自百度百科
在这棵树中 $17$ 和 $8$ 的LCA就是 $3$, $9$ 和 $7$ 的LCA就是 $7$ .
明白了LCA后,就下来我们就要探讨探讨LCA怎么求了 $qwq$
暴力算法
以 $17$ 和 $18$ 为例,既然要求LCA,那么我们就让他们一个一个向上爬(我要一步一步往上爬  -  -  "蜗牛"),直到相遇为止.第一次相遇即是他们的LCA. 模拟一下就是:
$17->14->1