前言
在做树上问题时，我们经常会遇到 (LCA)（最近公共祖先）问题。曾经的我遇到这类问题只会(O(n))暴力求解，学了倍增(LCA)，就可以(O(logn))解决了。
简介
倍增(LCA)，顾名思义，就是利用倍增来求解(LCA)（这真的是简介）。
主要思路
- 我们可以用(fa[i][j])来记录(i)的第(2^j)个祖先。
- 然后，对于每一次询问(LCA(x,y))，我们先找到(x)和(y)最近的深度相同的祖先。
- 接下来，我们先倍增找到最近的(x)和(y)的刚好为(2^j)的公共祖先。
- 然后，我们不断减小(j)，若当前(fa[x][j]!=fa[y][j])，我们就更新(x=fa[x][j])，(y=fa[y][j])，这样就可以保证修改后(fa[x][j]=fa[y][j])了。
一个简短的证明
因为我们已经保证修改前的(fa[x][j+1]=fa[y][j+1])了
并且，显然可得，(fa[fa[x][j]][j]=fa[x][j+1])，(fa[fa[y][j]][j]=fa[y][j+1])（(x)的第(2^j)个祖先的第(2^j)个祖先即为(x)的第(2^{j+1})个祖先，(y)同理）
因此，修改后的(fa[x][j])和(fa[y][j])就等同于修改前的(fa[x][j+1])和(fa[y][j+1])
得证，我们可以保证修改后(fa[x][j]=fa[y][j])
- 最后返回(fa[x][0])即可。
代码
inline int LCA(int x,int y)//求x和y的最近公共祖先
{
register int i;int k;
if(dep[x]<dep[y]) swap(x,y);//比较x和y的深度，选择深度较大的节点，寻找它的与深度较小的节点深度一样的祖先
for(i=0;dep[x]^dep[y];++i) if((dep[x]^dep[y])&(1<<i)) x=fa[x][i];//如上
if(!(x^y)) return x;//如果x==y，返回x
for(k=0;fa[x][k]^fa[y][k];++k);//我们先倍增找到最近的x和y的刚好为2^j的公共祖先
for(;k>=0;--k) if(fa[x][k]^fa[y][k]) x=fa[x][k],y=fa[y][k];//不断减小j，若当前fa[x][j]!=fa[y][j]，我们就更新x=fa[x][j]，y=fa[y][j]
return fa[x][0];//最后返回x的父亲
}