1. 何谓LCA

LCA(Least Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先。

img

如图,1和7的公共祖先有5和10,而它们的LCA是5。

2. 怎么求LCA

题设:求节点a,b的LCA

思路1:从节点a遍历到根节点,再从b遍历到根节点,找到最先相遇的地方。复杂度:o(n)

思路2:倍增。具体怎么做底下讲。复杂度:o(log n)

3. 倍增求LCA

做法:程序开始时选取任意节点为树根,进行dfs,得到所有点的深度与pre[i][j]。何谓pre[i][j]?

pre[i][j]指节点i的第2的j次方个祖先

img2

如上图中,10的第1个祖先是9,第二个祖先是8,第三个祖先是7,第四个祖先是1。所以10的第2的0次方个祖先是9(2^0=1),10的第2的1次方个祖先是8(2^1=2),10的第2的2次方个祖先是1(2^2=4)。很显然,10没有2的3次方个祖先。所以pre[10][0]=9,pre[10][1]=8,pre[10][2]=1。

而且通过倍增的思想,我们不难发现i的第2的j次方个祖先就是i的第2的j-1次方个祖先的第2的j-1次方个祖先(不信你看图),所以pre[i][j]=pre[pre[i][j-1]][j-1]。

其实要搞懂这个也很简单
2^i = 2*2^(i-1) = 2^(i-1) + 2^(i-1)

懂了吧
所以:
i的第2的j次方个祖先就是i的第2的j-1次方个祖先的第2的j-1次方个祖先

有了这个规律,我们就可以在dfs中预处理所有的pre了!

而求LCA的思路就是:对于节点a和b,先把深度大的节点提升到深度小的节点的相同深度,然后把a和b同时往上提,每次能提多少提多少,每次提了以后要保证节点a!=节点b,提升的高度从大往小找(先找n,再找n/2,再找n/4,再找n/8,再找n/16……最后再找1)。
而最后LCA就是a(或b)的父节点。

具体实现看代码吧……

4. 例题与代码

HDU - 2586 How far away ?传送门= ̄ω ̄=

思路:对于点a和点b,他们的树上距离是唯一的,也是最小的(因为树上任意两点直接只有一条通路),距离为a到根节点的距离+b到根节点的距离-2×(a和b的lca到根节点的距离)(很明显我就不证了^_^)。

注意!点到根节点的距离不同于点的深度!下面的代码中,deep[i]指节点i的深度,而far[i]表示节点i到根节点的距离!都通过递增得到!(根节点到根节点的距离为0,根节点的深度也为0)

代码: