LCA

最近公共祖先

• 在线算法 倍增
• 离线算法 tarjan
• ST/RMQ算法

倍增法

• 预处理 $nlogn$
• 查询$logn$
  f[i][j]表示第i个节点向上跳$2^k$步的点
  f[i[j]=f[f[i][j-1]][j-1]
  bfs预处理出f[i][j]和每个节点的深度

预处理

int deep[N];
int f[N][21];
void bfs(int x){
	queue<int > q;
	q.push(x);
	deep[x]=1;
	while(!q.empty()){
		int re=q.front();
		q.pop();
		int k=head[re];
		while(k!=0){
			if(!deep[e[k].to]){
				deep[e[k].to]=deep[re]+1;
				q.push(e[k].to);
				f[e[k].to][0]=re;
				for(int i=1;i<=20;++i){
					f[e[k].to][i]=f[f[e[k].to][i-1]][i-1];
				}
			}
			k=e[k].next;
		}
	}
}

查找lca

int lca(int x,int y){
	if(deep[x]<deep[y]) swap(x,y);
	for(int i=20;i>=0;--i){
		if(deep[f[x][i]]>=deep[y]){
			x=f[x][i];
		}
	}
	if(x==y) return x;
	for(int i=20;i>=0;--i){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}

模板题

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
#define N 510000
int n,m,s;
struct node{
	int next;
	int to;
}e[N*2];
int arr;
int head[N];
void add(int u,int v){
	e[++arr].next=head[u];
	e[arr].to=v;
	head[u]=arr;
	return ;
}
int deep[N];
int f[N][21];
void bfs(int x){
	queue<int > q;
	q.push(x);
	deep[x]=1;
	while(!q.empty()){
		int re=q.front();
		q.pop();
		int k=head[re];
		while(k!=0){
			if(!deep[e[k].to]){
				deep[e[k].to]=deep[re]+1;
				q.push(e[k].to);
				f[e[k].to][0]=re;
				for(int i=1;i<=20;++i){
					f[e[k].to][i]=f[f[e[k].to][i-1]][i-1];
				}
			}
			k=e[k].next;
		}
	}
}
int lca(int x,int y){
	if(deep[x]<deep[y]) swap(x,y);
	for(int i=20;i>=0;--i){
		if(deep[f[x][i]]>=deep[y]){
			x=f[x][i];
		}
	}
	if(x==y) return x;
	for(int i=20;i>=0;--i){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n-1;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	bfs(s);
	for(int i=1;i<=m;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}

离线算法 tarjan

预处理O(n+m)
查询O(1)

预处理

建立一棵题目给出的关系树e[N]
建立一棵根据询问建立的询问树e_ask[N]

struct  node{
	int to;
	int next; 
}e[2*N];
int arr;
int head[N];
void add(int u,int v){
	e[++arr].next=head[u];
	e[arr].to=v;
	head[u]=arr;
}
struct ask{
	int to;
	int next;
	int id;//此查询的编号
}e_ask[2*N];
int head_ask[N];
void add_ask(int u,int v,int id){
	e_ask[++arr].next=head_ask[u];
	e_ask[arr].to=v;
	e_ask[arr].id=id;
	head_ask[u]=arr;
}

访问每一个节点的子树
让子树的fa指向自己
如果当前节点的子树都访问完时
访问此节点询问树
根据讯问树访问到的点

• 如果没有被访问过---跳过，之后一定会被他的另一节点访问（说明未访问到对面节点的旁支）
• 如果已经被访问---此查询答案为他的fa节点

int fa[N];
int find(int x){
	if(fa[x]!=x){ return fa[x]=find(fa[x]);}
	else return x;
}
bool visit[N];
int ans[N];
bool used[N];
void dfs(int x){
	visit[x]=1;
	int k=head[x];
	while(k!=0){
		if(!visit[e[k].to]){
			dfs(e[k].to);
			fa[e[k].to]=x;
		}
		k=e[k].next;
	}
	k=head_ask[x];
	while(k!=0){
		if(visit[e_ask[k].to]&&!used[e_ask[k].id]){
			used[e_ask[k].id]=1;
			ans[e_ask[k].id]=find(e_ask[k].to);
		}
		k=e_ask[k].next;
	}
}

为什么此查询的答案一定是他的fa节点

当一个节点根据询问树访问到一个已经被访问过的节点时
这两个节点一定是在他们的公共祖先上遍历下来的
在最近公共祖先建立的子树系统中
已经被访问的那一个节点的旁支已经被访问完
即：此旁支的所有节点的fa 都指向了这个最近公共祖先
由此得证

贴一波完整代码

#include<iostream> //离线 tarjan算法 
#include<cmath>
#include<cstdio>
#include<algorithm>
#define N 510000
using namespace std;
int n,m,s;
struct  node{
	int to;
	int next; 
}e[2*N];
int arr;
int head[N];
void add(int u,int v){
	e[++arr].next=head[u];
	e[arr].to=v;
	head[u]=arr;
}
struct ask{
	int to;
	int next;
	int id;
}e_ask[2*N];
int head_ask[N];
void add_ask(int u,int v,int id){
	e_ask[++arr].next=head_ask[u];
	e_ask[arr].to=v;
	e_ask[arr].id=id;
	head_ask[u]=arr;
}
int fa[N];
int find(int x){
	if(fa[x]!=x){ return fa[x]=find(fa[x]);}
	else return x;
}
bool visit[N];
int ans[N];
bool used[N];
void dfs(int x){
	visit[x]=1;
	int k=head[x];
	while(k!=0){
		if(!visit[e[k].to]){
			dfs(e[k].to);
			fa[e[k].to]=x;
		}
		k=e[k].next;
	}
	k=head_ask[x];
	while(k!=0){
		if(visit[e_ask[k].to]&&!used[e_ask[k].id]){
			used[e_ask[k].id]=1;
			ans[e_ask[k].id]=find(e_ask[k].to);
		}
		k=e_ask[k].next;
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<n;++i){
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	arr=0;
	for(int i=1;i<=m;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		add_ask(x,y,i);
		add_ask(y,x,i);
	}
	for(int i=1;i<=n;++i){ fa[i]=i;}
	dfs(s);
	for(int i=1;i<=m;++i){
		cout<<ans[i]<<endl;
	}
	return 0;
}

ST/RMQ算法

欧拉序+ST
O($n+m-nlogn$)
不打算学.....