LCA(最近公共祖先)

1.倍增法（線上算法）

2.Tarjan（離線算法）

注：

線上做法：讀一個詢問，處理一個，輸出一個

離線做法：讀完全部詢問，再全部處理完，再全部輸出

一、倍增法

1、 算法過程：

1.預處理出 fa[i,j] ,和 depth[i] 。( fa[i,j] 表示從i這個點向上跳2j到達的點，depth[i] 表示這個點在這課有根樹中的深度，同時要将 depth[0] 設定為0，友善代碼的書寫)。

2.先将兩個點跳到同一個深度。

3.讓兩個點同時向上跳，直到兩個點跳到其最近公共最先的下一層。（如果跳到同一層的話，不能确定是否是最近的）。

4.輸出fa[目前點][0]即為最近公共祖先節點。

注：通過遞歸的方式處理，可以先向上跳2j-1步，在向上跳2j-1步，那麼這樣的話，預處理是就可以寫成fa[i][j]=fa[fa[i][j-1]][j-1]。向上跳的過程有點類似于快速幂，拼湊出一個十進制值等于該節點到根節點距離的二進制數，如果 j 位為1，那麼就可以向上跳2j步。

2、時間複雜度

預處理：O(nlogn)

查詢：O(logn)

3、模闆：

參考例題（AcWing 1172. 祖孫詢問 ）

#include <bits/stdc++.h>
using namespace std;
const int N=40010,M=N*2;
int n,m;
struct node{
	int to,nex;
}edge[M];
int head[N],cnt;
int depth[N],fa[N][20];
int q[N];
void addedge(int u,int v)
{
	edge[cnt].to=v;
	edge[cnt].nex=head[u];
	head[u]=cnt++;
}
//預處理出depth，和fa數組 
void bfs(int root)
{
	memset(depth,0x3f,sizeof(depth));
	depth[0]=0;depth[root]=1;
	queue<int> q;
	q.push(root);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=edge[i].nex)
		{
			int v=edge[i].to;
			if(depth[v]>depth[u]+1)
			{
				depth[v]=depth[u]+1;
				q.push(v);
				fa[v][0]=u;
				for(int k=1;k<=15;k++)
					fa[v][k]=fa[fa[v][k-1]][k-1];
			}
		}
	}
}
//向上跳的實作 
int lca(int a,int b)
{
	if(depth[a]<depth[b]) swap(a,b);
	for(int k=15;k>=0;k--)
		if(depth[fa[a][k]]>=depth[b])//因為設定了depth[0]=0，是以不會跳過根節點
			a=fa[a][k];
	if(a==b) return a;
	for(int k=15;k>=0;k--)
		if(fa[a][k]!=fa[b][k])
		{
			a=fa[a][k];
			b=fa[b][k];	
		}	
	return fa[a][0];
}
int main()
{
	cin>>n;
	int root=0;
	memset(head,-1,sizeof(head));
	cnt=0;
	for(int i=1;i<=n;i++)
	{
		int u,v;
		cin>>u>>v;
		if(v==-1) root=u;
		else addedge(u,v),addedge(v,u);
	}
	bfs(root);
	
	cin>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		int p=lca(a,b);
		if(p==a) cout<<1<<endl;
		else if(p==b) cout<<2<<endl;
		else cout<<0<<endl; 
	}
}
           

二、Tarjan離線算法

1、算法步驟：

主要思想：這裡将整個樹分為三個部分，并用st數組标記每個點的屬于那個部分，st[i]==2，i這個點屬于搜尋且回溯過的點（綠色部分）；st[i]==1，i這個點正在被搜尋但未回溯；st[i]==0，i這個點還未被搜尋。

通過對st值為2的點進行向上合并，就可以實作将已搜尋過的點合并到正在搜尋的這條鍊上，找到最近公共祖先。

1.建立對應的樹，将所有問題存入一個結構體或者一個pair數組。

2.進行一個dfs，在回溯的時候利用并查集将節點合并到父結點上。

3.每進行一次搜尋，就将問題數組周遊一遍，如果有與目前點相關的問題的時候，判斷另一個點是否被搜尋且回溯，如果是，則将另一個點的并查集中的值存入存放答案的對應數組位置。

2、時間複雜度：

O(n+m) n個點，m條詢問

3、模闆

參考例題（AcWing 1171. 距離 ）

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N=10010,M=N*2;

struct node{
	int to,nex,w;
}edge[M];
int head[N],cnt;
int dis[N];
int n,m;
int p[N];
int res[M];
int st[N];
vector<PII> query[N];   // first存查詢的另外一個點，second存查詢編号

void addedge(int u,int v,int w)
{
	edge[cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].nex=head[u];
	head[u]=cnt++;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void bfs(int s)
{
	memset(dis,0x3f3f3f3f,sizeof(dis));
	queue<int> q;
	q.push(s);
	dis[s]=0;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i!=-1;i=edge[i].nex)
		{
			int v=edge[i].to;
			if(dis[v]==0x3f3f3f3f)
			{
				dis[v]=dis[u]+edge[i].w;
				q.push(v);
			}
		}
	}
}
void tarjan(int u)
{
	
    st[u] = 1;
    for(int i=head[u];i!=-1;i=edge[i].nex)
    {
    	int v=edge[i].to;
    	if(!st[v])
    	{
    		tarjan(v);
    		p[v]=u;
		}
	}
    for(int i=0;i<query[u].size();i++)
    {
    	PII p=query[u][i];
        int y = p.first, id = p.second;
        if (st[y] == 2)
        {
            int anc=find(y);
            res[id]=dis[u]+dis[y]-dis[anc]*2;
        }
    }
    st[u] = 2;
}

int main()
{
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    cnt=0;
    for(int i=1;i<=n-1;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
       	addedge(u,v,w);
       	addedge(v,u,w);
    }
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v; 
        if (u!=v)
        {
            query[u].push_back(PII(v,i));
            query[v].push_back(PII(u,i));
        }
    }
	
    for(int i=1;i<=n;i++) 
		p[i]=i;

    bfs(1);
    tarjan(1);
    for(int i=1;i<=m;i++)
    	cout<<res[i]<<endl;
    	
    return 0;
}
           

參考資料：

作者：yxc

連結：https://www.acwing.com/activity/content/code/content/154795/

來源：AcWing算法提高課