LCA是什么，能吃吗

---

基本概念：

---

祖先：有根树中，一个节点到根的路径上的所有节点被视为这个点的祖先，包括根和它本身公共祖先：对于点a和b，如果c既是a的祖先又是b的祖先，那么c是a和b的公共祖先深度：子节点的深度=父节点深度+1，一般我们定根的深度为1最近公共祖先：树上两个节点的所有公共祖先中，深度最大的那个称为两个点的最近公共祖先(LCA)

例子

在这样一张图中，我们来回答一些问题，加深对LCA的印象

4的祖先有哪些 答案：4，2，17的祖先有哪些 答案：7，5，3，19的祖先有哪些 答案：9，6，3，17和9的公共祖先有哪些 答案：3，17和9的最近公共祖先是哪个点 答案：34和9的最近公共祖先是哪个点 答案：1

（右拉查看答案）你做对了吗？

怎么求LCA

暴力

暴·法①

根据最近公共祖先LCA的定义，可以很容易想到这样一种方法来寻找a和b的LCA：

如果a和b的深度不同，那么将深度更大的那个点向根的方向移动一步，即选择它的父节点，重复这个过程直到两个点深度相同当a和b深度相同，但不是同一个点，那么各自向根的方向移动一步，即选择它们各自的父节点，重复这过程直到选择到同一个点

代码：

int LCA(int a,int b){ while(d[a]!=d[b]){ if(d[a]<d[b]){ b=f[b]; } else{ a=f[a]; } } while(a!=b){ a=fa[a]; b=fa[a]; } return a; }

暴·法②