最近公共祖先（LCA）

題目描述

如題，給定一棵有根多叉樹，請求出指定兩個點直接最近的公共祖先。

輸入格式

第一行包含三個正整數 N,M,S，分别表示樹的結點個數、詢問的個數和樹根結點的序号。

接下來 N−1 行每行包含兩個正整數 x,y，表示 x 結點和 y 結點之間有一條直接連接配接的邊（資料保證可以構成樹）。

接下來 M 行每行包含兩個正整數 a,b，表示詢問 a 結點和 b 結點的最近公共祖先。

輸出格式

輸出包含 M 行，每行包含一個正整數，依次為每一個詢問的結果。

輸入輸出樣例

輸入 #1

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
           

輸出 #1

4
4
1
4
4
           

說明/提示

對于 30% 的資料，N≤10，M≤10。

對于 70% 的資料，N≤10000，M≤10000。

對于 100% 的資料，N≤500000，M≤500000。

視訊詳解：最近公共祖先（LCA）問題_哔哩哔哩_bilibili

算法一：樸素算法1（70分）

dfs求每個節點的父節點，然後lca找最近公共子節點！！！

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int N,M,S;
bool vis[500005];
int deep[500005];//多餘
int father[500005];
vector<int>head[500005];
int k=0;
void dfs(int s){
	for(int i=0;i<head[s].size();i++){
		vis[s]=true;
		int v=head[s][i];
		if(!vis[v]){
			father[v]=s;
			deep[v]=deep[s]+1;
			dfs(v);
		}
		
	}
}
int lca(int x,int y){
	memset(vis,false,sizeof(vis));
	while(x){
		vis[x]=true;
		x=father[x];
	}
	while(y){
		if(vis[y]) return y;
		y=father[y];
	}
}
int main(){
	scanf("%d%d%d",&N,&M,&S);
	for(int i=1;i<N;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		head[x].push_back(y);
		head[y].push_back(x);
	}
	deep[S]=0;
	father[S]=0;
	vis[S]=true;
	dfs(S);
	for(int i=0;i<M;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	}
}
           

算法二：樸素算法2（100分）

dfs求每個節點的深度和父節點，然後lca找最近公共子節點！！！

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int N,M,S;
bool vis[500005];
int deep[500005];
int father[500005];
vector<int>head[500005];
int k=0;
void dfs(int s){
	for(int i=0;i<head[s].size();i++){
		vis[s]=true;
		int v=head[s][i];
		if(!vis[v]){
			father[v]=s;
			deep[v]=deep[s]+1;
			dfs(v);
		}
		
	}
}
int lca(int x,int y){
	if(deep[x]<deep[y]) swap(x,y);
	while(deep[x]>=deep[y]){
		//cout<<x<<' '<<y<<endl;
		if(deep[x]==deep[y]){
			if(x==y) return x;
			if(father[x]==father[y]) return father[x];
		}
		if(deep[x]!=deep[y]) x=father[x];
		else{
			x=father[x];y=father[y];
		}
	}
	//memset(vis,false,sizeof(vis));
	/*while(x){
		vis[x]=true;
		x=father[x];
	}
	while(y){
		if(vis[y]) return y;
		y=father[y];
	}*/
}
int main(){
	scanf("%d%d%d",&N,&M,&S);
	for(int i=1;i<N;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		head[x].push_back(y);
		head[y].push_back(x);
	}
	deep[S]=0;
	father[S]=0;
	vis[S]=true;
	dfs(S);
	for(int i=0;i<M;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	}
}
           

算法三：倍增法

倍增算法可以線上求樹上兩個點的LCA，時間複雜度為O(nlogn) 。

#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
using namespace std;
int N,M,S;
bool vis[500005];
int deep[500005];
int father[500005];
vector<int>head[500005];
int f[500005][30]; 
int k=0;
void dfs(int s){
	for(int i=0;i<head[s].size();i++){
		vis[s]=true;
		int v=head[s][i];
		if(!vis[v]){
			f[v][0]=s;
			deep[v]=deep[s]+1;
			dfs(v);
		}
		
	}
}
int lca(int x,int y){
	if(deep[x]<deep[y]) swap(x,y);
	for(int i=log2(deep[x]-deep[y]);i>=0;i--){
		if(deep[x]-deep[y]>=(1<<i)){
			x=f[x][i];
		}
	}
	if(x==y) return x;
	for(int i=log2(deep[x]);i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
int main(){
	scanf("%d%d%d",&N,&M,&S);
	for(int i=1;i<N;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		head[x].push_back(y);
		head[y].push_back(x);
	}
	deep[S]=0;
	father[S]=0;
	vis[S]=true;
	dfs(S);
	for(int i=1;i<=22;i++){
		for(int u=1;u<=N;u++){
			f[u][i]=f[f[u][i-1]][i-1];
		}
	}
	for(int i=0;i<M;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	}
}