最近公共祖先（LCA）

一道板题

倍增求LCA

维护数组 \(f[ i ][ j ]\) 表示\(i\) 号节点的第\(2^j\) 级祖先，没有则为\(0\)

转移方程：

• 相同深度求LCA:

将k从大到小循环，如果\(x\)，\(y\) 的\(2^k\) 级祖先相同则不做改变，不同则将 \(x\) ，\(y\) 更新为各自的\(2^k\) 级祖先。

当 \(k=0\) 时，LCA为此时 \(x\) ，\(y\) 的父亲

• 不同深度求LCA:

令 \(dep[a]>dep[b]\) ，将 \(a\) 向上跳，直到 \(a\) 的深度与 \(b\) 的深度相同为止，于是变转换为 相同深度求 LCA

时间复杂度：
预处理： \(O(nlogn)\) ，单词询问： \(O(logn)\)

空间复杂度： \(nlogn\)

代码示例：

预处理：

void bfs(int root){
	memset(d,0x3f,sizeof d);
	d[root]=1,d[0]=0;
	queue q;
	q.push(root);
	
	while(q.size()){
		int t=q.front();
		q.pop();
		
		for(int i=h[t];i;i=nxt[i]){
			int x=en[i];
			if(d[x]>d[t]+1){
					d[x]=d[t]+1;
				   q.push(x);
				   f[x][0]=t;
				   for(int j=1;j<=15;j++)
						f[x][j]=f[f[x][j-1]][j-1];
			}
		}
	}
}

主体：

int lca(int a,int b){
	if(d[a]=0;i--)
		if(d[f[a][i]]>=d[b])	a=f[a][i];
	
	if(a==b)	return a;
	
	for(int i=15;i>=0;i--)
		if(f[a][i]!=f[b][i])
			a=f[a][i],b=f[b][i];
	    
	return f[a][0];
}
    

tarjan求LCA

利用递归的回溯做标记，遍历一次后标记为\(1\) ，回溯后标记为\(2\)

把询问转换成离线做法，先把所有的询问存下来，最后统一输出

优化用到了并查集的思想，回溯后将此点与其父亲节点合并，答案返回集合的父亲节点

代码示例：

存询问：

void add_qu(int a,int b,int i){
	qu[a].push_back(b),id[a].push_back(i);
	qu[b].push_back(a),id[b].push_back(i);
}

主体：

void targan(int x){
	v[x]=1;
	for(int i=h[x];i;i=nxt[i]){
		int y=en[i];
		if(v[y])	continue;
		targan(y);
		f[y]=x;
	}
	
	for(int i=0;i

#include
using namespace std;

const int N=5e5+5,M=N*2;
int h[N],nxt[M],en[M],m;
vector qu[N],id[N];
int root;
int v[N],ans[N],f[N];

void add(int a,int b){
	nxt[++m]=h[a],en[m]=b,h[a]=m;
}
void add_qu(int a,int b,int i){
	qu[a].push_back(b),id[a].push_back(i);
	qu[b].push_back(a),id[b].push_back(i);
}

int get(int x){
	if(f[x]==x)	return x;
	return f[x]=get(f[x]);
}

void targan(int x){
	v[x]=1;
	for(int i=h[x];i;i=nxt[i]){
		int y=en[i];
		if(v[y])	continue;
		targan(y);
		f[y]=x;
	}
	
	for(int i=0;i