P3379傳送門
首先明确一下什麼叫做最近公共祖先 對于一個樹來說 最近公共祖先是兩個結點的公共祖先中距離根結點最遠的那個祖先 也可以說成是深度最大的那個公共祖先
思路
我們先用最樸素的想法來思考
如果你想找到一個最近公共祖先 那是不是先得讓這兩個結點爬到同一高度的時候 然後再去比較這他倆是不是同一個點呢？
①如果當他們處于同一個高度而且還是同一點的話 我們是不是就找到了他倆的最近公共祖先 就是這個點
②如果不是的話 我們是不是還得讓這兩個點往上爬 每爬一步就去比較這兩個點是不是同一個點 直到兩個點是同一個點的時候 那麼此時就是最近公共祖先
這有個暴力的代碼 看一下這個相對來說比較好了解點
AC代碼1暴力
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+6;
int dep[maxn];
int fa[maxn];
vector<int>edge[maxn];
void dfs(int u,int v)
{
dep[u]=dep[v]+1;
fa[u]=v;
for(int i=0;i<edge[u].size();i++)
{
int p=edge[u][i];
if(p!=v)
{
dfs(p,u);
}
}
}
int lca(int a,int b)
{
if(dep[a]<dep[b]) swap(a,b);
while(dep[a]!=dep[b])
{
a=fa[a];
}
if(a==b) return a;
while(a!=b)
{
a=fa[a];
b=fa[b];
}
return a;
}
int main()
{
int n,m,s,x,y;
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n-1;i++)
{
scanf("%d%d",&x,&y);
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(s,0);
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
printf("%d\n",lca(a,b));
}
return 0;
}
再用倍增的思路來想
1.因為這是一步一步的走 我們能不能優化一下呢 能不能一步多走點
這個時候我們就需要用到這個數組f[i][j] 它表示的意思是結點 i向上爬了2^j次下所在的結點
比如上圖那個樹來說 f[2][0]=4 f[1][0]=4 f[3][1]=4 f[5][1]=4
2.對于數組f[i][j]來講它的公式可以這樣寫f[i][j]=f[i][f[i][j-1]][j-1]
為什麼這樣寫呢 f[i][j-1]的意思就是結點i跳了2^j-1下後所在的結點 那麼它再從此結點跳2^j-1下 是不是就相當于從i跳了2^j下？
因為 2^j== (2^(j-1))*2 所有就有了這個遞推公式f[i][j]=f[i][f[i][j-1]][j-1]
3.下面我們來看這個倍增法每部分代碼的含義
①dfs(u,v)其實也就是預處理 求最近公共祖先前 你需要知道每個結點的深度以及每個結點跳2^j次下後它的祖先
②lca(a,b)就是用倍增法找任意倆個結點a,b的最近公共祖先
首先我們需要做的是讓這兩個結點爬的同一深度(其實就是讓深度最深的那個結點往上爬）
可能又有人問了 為什麼循環的時候是從29往0循環呢 而不是從0往29循環呢 我們都知道任何一個正數我們都可以用二進制來表示 那麼這兩者之間的深度差是不是也可以用二進制來表示？
就拿5來說 5是不是可以表示為101
如果我們從0到29這樣循環 那這個2^1這個地方你跳不跳？如果你跳的話 我們就不能到達同一個深度
但是如果我們從29到0這樣循環的話我們就可以先跳一個2^2
再跳一個2^0 其中那個2^1就不需要跳了就可以到達同一個深度 你可以自己在心裡想想這個地方 為啥要逆着來的
當兩個結點再同一個高度的時候 可以先比較兩者是不是同一個結點 如果是就直接輸出 如果不是的話 兩者一起再往上跳直到跳的最近公共祖先的孩子結點時候就停止 然後輸出他們的父節點進行了也就是f[a][0]
可能這個地方又有人問了 為啥非得跳到最近公共祖先的孩子結點呢 為啥不直接跳到最近公共祖先啊 我認為如果讓他倆之間都跳到公共祖先的時候 有可能不是最近公共祖先 有可能直接跳的更遠了跳過了 我認為這個地方其實跟上面那個二進制那有點相似自己多想想應該沒問題
AC代碼2倍增
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+7;
int dep[maxn];//結點深度
int f[maxn][30];//f[i][j]結點i跳2^j次後所在結點
ll bit[30];//bit[i]代表為2^i次方
int n,m;
vector<int>edge[maxn];
void init()
{
bit[0]=1;
for(int i=1;i<=29;i++)
{
bit[i]=bit[i-1]<<1;
}
}
void dfs(int u,int v)//預處理
{
dep[u]=dep[v]+1;
f[u][0]=v;
for(int i=1;bit[i]<=dep[u];i++)
{
f[u][i]=f[f[u][i-1]][i-1];
}
for(int i=0;i<edge[u].size();i++)
{
int p=edge[u][i];
if(p!=v)
{
dfs(p,u);
}
}
}
int lca(int a,int b)
{
if(dep[a]<dep[b]) swap(a,b);
for(int i=29;i>=0;i--)
{
if(dep[a]-dep[b]>=bit[i])
{
a=f[a][i];
}
}
if(a==b) return a;
for(int i=29;i>=0;i--)
{
if(f[a][i]!=f[b][i])//如果讓他倆相等的話有可能就不是最近公共祖先了
{
a=f[a][i];
b=f[b][i];
}
}
return f[a][0];
}
int main()
{
int n,m,s,x,y;
memset(dep,0,sizeof(dep));
init();
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=n-1;i++)
{
scanf("%d%d",&x,&y);
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(s,0);
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
printf("%d\n",lca(a,b));
}
return 0;
}
兩者比一下還是倍增法速度比較快 如果思路不正确可以指出來 代碼也不知道咋過了