最近公共祖先_牛客博客

倍增LCA

时间和空间复杂度分别是 O((n+q)logn) 和 O(nlogn) 。
1.DFS求每个节点的深度
2.倍增跳跃祖先节点预处理
3.如果两节点不在同一高度，则让较深的高度u跳跃到较浅的高度v来。
4.两个节点同时跳跃，先从大的跳跃幅度开始。
5.直到最后跳跃到最近公共祖先的下一层为止

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=1e3+5;
int father[maxn][40]={0};
vector<int> g[maxn];
int depth[maxn]={0};
int n,m;
int visit[maxn];
int inDeg[maxn];
void dfs(int u){
	visit[u]=1;
	for(int j=0;j<g[u].size();j++){
		int v = g[u][j];
		if(!visit[v]){
			depth[v]=depth[u]+1;
			dfs(v);
		}
	}  
}  //深搜，求出各点的深度 

void bz(){  //倍增 
	for(int j=1;j<=30;j++){
		for(int i=1;i<=n;i++){
			father[i][j] = father[father[i][j-1]][j-1];
		}
	}
} 

int LCA(int u,int v ){  //u，v是顶点编号 
	if(depth[u] < depth[v]) swap(u,v); //保证深度最大的点为u
	int d = depth[u] - depth[v];
	
	for(int i=0;i<=30;i++){  //使较深的点u跟v高度一致 
		if( (1<<i) & d)  u = father[u][i];
	} 
	if(u == v) return v;//如果深度一样时，两个点相同，则说明u在v的下面，直接返回。
	for(int i=29;i>=0;i--){
		if(father[u][i] != father[v][i]){  //如果两个值不等时，按照同样的速度往上跳 
			u = father[u][i];  
			v = father[v][i];
		}  //注意，这里没有直接跳出，而是反复跳到最近公共祖先的下一层为止才退出
	} 
	return father[u][0]; //再往上走一层就是最近公共祖先 
}
int main(){
	int u,v,x,y;
	scanf("%d %d",&n,&m);
	while(m--){
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		inDeg[v]++;
		father[v][0]=u;
	} 
	scanf("%d%d",&x,&y);
	int root=0;
	for(int i=1;i<=n && root==0;i++){
		if(inDeg[i]==0) root = i;
	}
	dfs(root);
	bz();
	
	int ans = LCA(x,y);
	printf("%d\n",ans);
	return 0;
}

输入样例
5 4
1 3
2 3
3 4
3 5
4 5
输出样例
3
解释：
题目有5个顶点，4条边，查询4节点和5节点的最近公共祖先
输出结果为3

Tarjan

离线算法：先读入所有查询，在一次遍历中，把所有询问一次性解决。
时间复杂度： $O (n + q)$
P3379 【模板】最近公共祖先（LCA）
有3个测试点没过，懒得改了，等以后有时间了再修改吧。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e+5;
int f[maxn];
bool vis[maxn];
vector<int> G[maxn],Q[maxn];
struct qnode{
	int x;
	int y;
	int lca;
}query[maxn];
void init(){ //并查集初始化 
	for(int i=0;i<maxn;i++){
		f[i] = i;
	}
}
int find(int x){ //并查集的查找 
	if(f[x] == x) return x;
	else return f[x] = find(f[x]);
}
void dfs(int u) {
	vis[u] = true; 
	for(auto v : Q[u]){
		if(query[v].x == u){  //说明u就是当初存入的x，而需要查询的是y 
			if(vis[query[v].y]){
				query[v].lca = find(query[v].y); 
			}
		}else{
			if(vis[query[v].x]){
				query[v].lca = find(query[v].x); 
			}
		}
	}
	
	for(auto v : G[u]){
		if(vis[v]) continue; //父节点 跳过 
		dfs(v);
		f[v] = u;
		
	}
}
int main(){
	init();
	int n,m,s;
	scanf("%d%d%d",&n,&m,&s);
	int x,y;
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	} 
	for(int i=1;i<=m;i++){
		scanf("%d%d",&query[i].x,&query[i].y);
		Q[query[i].x].push_back(i); //保存的是结构体的序号，每个结构体序号中有两个元素x,y 
		Q[query[i].y].push_back(i);
	}
	dfs(s);
	for(int i=1;i<=m;i++){
		printf("%d\n",query[i].lca);
	}
	return 0;
}