Lca的四种写法(1) 树上倍增

#LCA专题之树上倍增

LCA(Lowest Common Ancestors)即最近公共祖先。在图论中，我们往往需要解决一些树上的操作，而很多时候我们需要求出某两个结点的最近公共祖先

我们可以构建一个类似st表的东西来存储他的祖先，fa[i][j]表示i号节点上面的 1«j 的祖先，而i号结点的父亲就是fa[i][0]了， i号结点父亲的父亲就是fa[i][1]了。

具体做法是，先用邻接表存图。我习惯于tot从2开始存边，这样第j条边的反边就是的编号就是j^1，这在网络流中很好用。 预处理 1、dfs一遍求出每个结点的父亲和深度 2、倍增2的整数次幂的祖先 对于每个询问 1、将两个结点提到统一高度 2、再同时往上爬直到LCA

时间复杂度O(nlogn)

struct Edges{
	int s,t,nxt;
	Edges(){
		s = t = nxt = 0;
	}
	Edges(int _s,int _t,int _nxt):s(_s),t(_t),nxt(_nxt){}
}e[M*2];
int tot = 1,head[N]；
inline void add(int s,int t){
	e[++tot] = Edges(s,t,head[s]);
	head[s] = tot;
	e[++tot] = Edges(t,s,head[t]);
	head[t] = tot;
}

然后dfs建树，dfs的同时记录每个点的深度用dep[i]表示结点i的深度，根节点的深度我们可以为0，也可以为1，我这里的写法是根节点深度为0的写法 dfs 的过程我们需要找到每个结点的父亲，也就是记录fa[i][0]。

void dfs(int r){
	int v;
	vis[r] = 1;//标记是否访问
	for(int i=head[r];i;i = e[i].nxt){
		v = e[i].t;
		if(!vis[v]){
			dep[v] = dep[r]+1;
			fa[v][0] = r;//记录v点的父亲
			dfs(v);
		}
	}
}

dfs完了之后需要进行倍增，找出每个点的i的整数次方的祖先，倍增代码如下，其实是一种递推。

for(int j=1;j<=17;++j){
		for(int i = 1;i<=n;++i){
			fa[i][j] = fa[fa[i][j-1]][j-1];
		}
	}

inline int lca(int s,int t){
	if(dep[s]>dep[t])swap(s,t);//我们需要求出两个结点深度的差，并将其提到统一高度
	int len = dep[t] - dep[s],x = 0,tmp = 0;
	while(len){
		x = lowbit(len);
		tmp = log2(x);//log2(x)返回以2为底x的对数，C++标准库函数
		t = fa[t][tmp];
		len-=x;
	}
	if(s == t)return s;
	len = log2(dep[t])+1;
	for(;len>=0;--len){
		if(fa[s][len] != fa[t][len]){//保证不会超过LCA
			s = fa[s][len];
			t = fa[t][len];
		}
		else continue;
	}
	return fa[s][0];//最后一次爬完的父亲就是LCA
}

以上就是求LCA的树上倍增算法

有空再配图