LCA

定义

LCA（Least Common Ancestors），即最近公共祖先，指对于有根树 TT 的两个结点 uu 、vv ，最近公共祖先 LCA(T,u,v)LCA(T,u,v) 表示一个结点 xx, 满足 xx 是 uu、vv 的祖先且 xx 的深度尽可能大。

法一：跳跃法

·先尝试跳16格、再尝试8格、再尝试4格……

·预处理f[x][t]表示节点x的第2^t个祖先

void dfs(int x, int fa){
	anc[x][0] = fa;
	depth[x] = deth[fa] + 1;
	for(int i = 1; i < M; ++i)
		anc[x][i] = anc[anc[x][i-1]][i-1];
	for(int i = head[x]; i; i = e[i].next)
		if(e[i].v != fa)
			dfs(e[i].v, x);
}//预处理
int LCA(int x, int y){
	//将x和y拉到同一水平线上来 
	if(depth[x] < depth[y])swap(x, y);
	for(int i = M - 1; i >= 0; --i){
		if(depth[anc[x][i]] >= depth[y])//如果x跨2^i步没超过y 
			x = anc[x][i];
	}
	if(x == y)return x;
	for(int i = M - 1; i >= 0; --i)
		if(anc[x][i] != anc[y][i]){
			x = anc[x][i];
			y = anc[y][i];
		}
	return anc[x][0];//此时x和y不一样，但是父亲一样 
}