倍增求LCA（最近公共祖先）

定义

LCA(Least Common Ancestors），最近公共祖先，如节点$z$z是$x，y$x，y的祖先，则称$z$z是$x,y$x,y的公共祖先，深度最最大的公共祖先称为$LCA$LCA。
比如说：

$LCA$LCA（4，5）=2，$LCA$LCA（5，6）=1，$LCA$LCA（2，3）=1。

懂了？

如何求LCA

暴力方法很容易得到。
我们用$dfs$dfs求出点的深度$d$d
只要每次将自己的深度赋为自己父亲的深度+1即可。

然后深度大的先一步一步跳，跳的与另一个节点深度一样。
然后……两个一起跳，跳到一起，当前节点就是$LCA$LCA。

但是万一这个距离有点大，一步步跳超时怎么办？

正题：倍增法

我们设$f[i][j]$f[i][j]代表i号节点的$2^j$2j辈祖先（就是往上爬$2^j$2j步）。
如果没有这个祖先（爬过根节点了）就设为0（不存在）。

很容易得到一条等式
$f[i][j]=f[f[i][j-1]][j-1]$f[i][j]=f[f[i][j−1]][j−1]
因为$i$i往上爬$2^j-1$2j−1再爬$2^j-1$2j−1就是直接往上爬$2^j$2j步。
还有$f[i][0]$f[i][0]就是自己的父节点（往上走一步就是自己的节点）

以上是预处理。

实现

void dg(int u,int father)//u开始为根节点，father开始为0（根节点的父节点不存在）
{
	int i;
	d[u]=d[father]+1;//深度是自己父亲加1
	for (i=0;i<=19;i++) 
		f[u][i+1]=f[f[u][i]][i];//当前节点的f数组更新（此时f[u,i]已知）
	for (i=head[u];i;i=next[i])//枚举出边
	{
		if (e[i]==father) continue;//因为是无向图，所以无向存图，会建立反向边，
								   //指向父节点，就要判断是否指向父节点
		f[e[i]][0]=u;//子节点往上跳2^0=1步就是自己
		dg(e[i],u);//递归子树
	}	
}

那么自然还要求$LCA$LCA是吧。

设要求$LCA$LCA（$x$x,$y$y）（使得$d[x]$d[x]>$d[y]$d[y],否则可交换）
算法流程大概是这样:
先把$x$x跳到和$y$y同深度
跳2^logn步……，$2^1$21步，$2^0$20步。
然后两个一起……
跳2^logn步……，$2^1$21步，$2^0$20步。
跳到了！

int lca(int x,int y)
{
	int i;
	if (d[x]<d[y]) swap(x,y);//使深度保证d[x]>=d[y]
	for (i=20;i>=0;i--)
	{
		if (d[f[x][i]]>=d[y])//保证没跳过头 
			x=f[x][i];//跳
		if (x==y) return x;//万一跳到同一层就重合了，直接退出
	}
	for (i=20;i>=0;i--)
	{
		if (f[x][i]!=f[y][i])//两点一起跳还没重合
		{
			x=f[x][i];//跳
			y=f[y][i];
		}
	}
	return f[x][0];//两点还没重合，只是跳完了，它们共有的父节点就是LCA
}

谢谢，有疑问私聊。