洛谷 P3379 【模闆】最近公共祖先（LCA）

洛谷 P3379

題目

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

輸入

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

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

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

輸出

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

樣例

input

5 5 4

3 1

2 4

5 1

1 4

2 4

3 2

3 5

1 2

4 5

output

4

4

1

4

4

說明/提示

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

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

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

樣例說明：

該樹結構如下：

第一次詢問：2,4 的最近公共祖先，故為 4。

第二次詢問：3,2 的最近公共祖先，故為 4。

第三次詢問：3,5 的最近公共祖先，故為 1。

第四次詢問：1,2 的最近公共祖先，故為 4。

第五次詢問：4,5 的最近公共祖先，故為 4。

故輸出依次為 4,4,1,4,4。

解題思路

假設我們要求 x x x, y y y的最小公共祖先

很容易想到先讓深度大的那個往上走

x x x, y y y深度一樣後，再同時一步一步再接着一步

直到找到一個共同的祖先

但是這樣的查詢一次就是 O O O（ n n n）

看題目就知道要學一個東東叫 L C A LCA LCA

也就是用來求最小公共祖先的算法

先學一下倍增這個概念

通過倍增可以想到，我們一次可以跳不止一步

我們可以讓它一次就跳2^ j j j步（保證跳完之後沒有超過邊界，也不會跳過最小的公共祖先）

設 f f f[ i i i][ j j j]以 i i i為目前節點，跳了2^ j j j步後對應的節點

• f f f[ i i i][0]=它的父節點
• f f f[ i i i][ j j j]= f f f[ f f f[ i i i][ j j j-1]][ j j j-1] 跳了一半再一半

代碼

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
struct hhx{
	int to,next;
}a[1000100];
int t,n,m,s,x,y;
int f[500100][50],head[500100],dep[500100];
void add(int x,int y)  //連接配接 
{
	 a[++t].to=y;
	 a[t].next=head[x];
	 head[x]=t;
}
void dfs(int d,int fa)
{
	 f[d][0]=fa;   //走一步，到父節點 
	 dep[d]=dep[fa]+1;  //累加深度 
	 for (int i=head[d];i;i=a[i].next)  //枚舉子節點 
	     if (a[i].to!=fa) dfs(a[i].to,d);  //繼續往下走 
}
int lca(int x,int y)
{
	if (dep[x]>dep[y])
	   swap(x,y);
	int c=dep[y]-dep[x],j=19,t=1<<j;
	while (c)
	{
		  if (c>=t)
		  {
		  	 y=f[y][j];
		  	 c-=t;
		  }
		  t/=2;
		  j--;
	}  //使x,y深度相同
	if (x==y)  //x就是x,y的最小公共祖先
	   return x;
	j=19;
	while (j>=0)  //同時走
	{
		  if (f[x][j]!=f[y][j])
		  {
		  	 x=f[x][j];
		  	 y=f[y][j];
		  }
		  j--;
	}
	return f[x][0];
} 
int main()
{
	scanf("%d%d%d",&n,&m,&s); 
	for (int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(s,0);
	for (int j=1;j<20;j++)  //枚舉步數，2^20夠了
	    for (int i=1;i<=n;i++)  //枚舉點 
		    f[i][j]=f[f[i][j-1]][j-1]; //等于以走了一半的那個點作為起點，再走了一半 
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	} 
}