[ Lowest Common Ancestor , LCA Doubling Search ] 最近共同祖先倍增演算法

首先建立一張倍增表，pa[i][x]表示x的第$2^i$的祖先，若不存在則為$-1$，可以在DFS或BFS的過程中求得，複雜度為$\ord{N*MAX\_LOG}$

對於每筆詢問，我們可以利用剛剛求得的倍增表，在$\ord{MAX\_LOG}$的時間在線查詢
先將要查詢的a,b兩點較深的點移至較淺的點的深度，之後二分搜LCA的位置
附上模板:

	#define MAXN 100000
	#define MAX_LOG 17
	typedef vector<int >::iterator VIT;
	int pa[MAX_LOG+1][MAXN+5],dep[MAXN+5];
	vector<int >G[MAXN+5];
	void dfs(int x,int p){
	pa[0][x]=p;
	for(int i=0;i+1<MAX_LOG;++i){
	pa[i+1][x]=pa[i][pa[i][x]];
	}
	for(VIT i=G[x].begin();i!=G[x].end();++i){
	if(*i==p)continue;
	dep[*i]=dep[x]+1;
	dfs(*i,x);
	}
	}
	inline int find_lca(int a,int b){
	if(dep[a]>dep[b])swap(a,b);
	for(int i=dep[b]-dep[a],k=0;i;i/=2){
	if(i&1)b=pa[k][b];
	++k;
	}
	if(a==b)return a;
	for(int i=MAX_LOG;i>=0;--i){
	if(pa[i][a]!=pa[i][b]){
	a=pa[i][a];
	b=pa[i][b];
	}
	}
	return pa[0][a];
	}

view raw Doubling Search.cpp hosted with ❤ by GitHub