概念引入
- 最近公共祖先简称 \(LCA\)（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。
在下面的说明中，我们设两个节点分别为 \(x\),\(y\)，节点 \(x\),\(y\) 的深度分别表示为 \(dep_x\),\(dep_y\),将树称为 \(T\)
算法详解:
朴素算法：
先将节点 \(x\) 的深度提升到与 \(y\) 节点深度相同的位置，然后两个一起一个一个往上跳，直到相遇。
那么易知时间复杂度为 \(O(n)\)，因为过于朴素，这里就不给出代码了。
倍增算法：
对于朴素算法中的：
“然后两个一起一个一个往上跳”
我们可以用倍增的方式完成跳跃.
那么如何实现呢?
我们知道,任何一个非负整数都可以进行二进制拆分.例如:
- \(7 = 2 ^ 0 + 2 ^ 1 + 2 ^ 2\)
- \(14 = 2 ^ 1 + 2 ^ 2 + 2 ^ 3\)
那么如果需要向上跳的次数为 \(n\),则朴素算法的时间复杂度为 \(O(n)\),而倍增算法的复杂度就可以达到\(O(log_2 n)\).
( 对于将 \(x\),\(y\) 提升到同一高度的过程,同样可以使用倍增的算法来实现,这里不多加说明 )
接下来考虑如何实现
我们设 \(fa_{x,i}\) 为 \(x\) 节点的 \(2 ^ i\) 级的祖先,即 \(x\) 节点向上走 \(2 ^ i\) 步所到达的节点
- 预处理 \(fa\) 数组:
我们知道:\(2 ^ n = 2 ^ {n-1} * 2 ^ {n - 1}\)
那么我们可以将向上走 \(2 ^ i\) 步看作先走 \(2 ^ {i - 1}\) 再走 \(2 ^ {i - 1}\) 步
则有: \(fa_{x,i} = fa_{fa_{x,i - 1},i - 1}\) 这可以说是非常关键的一步
因为 \(\forall x \in T\) , \(fa_{x,0}\) (即 \(x\) 的父节点)都可以通过一遍 \(dfs\) 解决
for(int i = 1;i <= log2(n);i++){
for(int j = 1;j <= n;j++){
fa[j][i] = fa[fa[j][i - 1]][i - 1];
}
}
- 将 \(x\),\(y\) 提升到同一高度:
主要思想是将 \(x\),\(y\) 的深度差值进行二进制拆分
if(dep[x] < dep[y]) swap(x,y);//保证x的深度大于y,方便后面的计算
int delta = dep[x] - dep[y];
for(int i = 0;i <= log2(n);i++){
if((1 << i) & delta) x = fa[x][i];//向上跳,本质是对delta进行二进制拆分
}
- \(x\),\(y\) 同时向上跳
这里有一个细节,即是将 \(i\) 从 \(log_2 n\) 往 \(0\) 枚举,这样可以避免拆分的重复或漏
for(int i = log2(n);i >= 0;i--){
if(fa[x][i] != fa[y][i]){
//Leap!
x = fa[x][i];
y = fa[y][i];
}
}
我们可以将第二步和第三步封装成一个函数:
int lca(int x,int y){
if(dep[x] < dep[y]) swap(x,y);
int delta = dep[x] - dep[y];
for(int i = 0;i <= log2(n);i++){
if((1 << i) & delta) x = fa[x][i];
}
if(x == y){
return x;
}
for(int i = log2(n);i >= 0;i--){
if(fa[x][i] != fa[y][i]){//这里最终跳跃到的是lca(x,y)的子节点
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
那么我们的倍增算法就好了,可知其时间复杂度为 \(O(log_2 n)\)
这里附上完整代码：
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 7;
const int LOG = 30;
int n,m,r;
int dep[MAXN];
int fa[MAXN][LOG];
bool vis[MAXN];
vector<int> tree[MAXN];
void dfs(int root){
vis[root] = true;
if(tree[root].size() == 0){
return;
}
for(int to : tree[root]){
if(!vis[to]){
dep[to] = dep[root] + 1;
fa[to][0] = root;
dfs(to);
}
}
}
int lca(int x,int y){
//Leap to a same depth:
int dx = dep[x],dy = dep[y];
if(dep[x] != dep[y]){
if(dx < dy){
swap(dx,dy);
swap(x,y);
}
int delta = dx - dy;
for(int i = 0;i <= LOG - 2;i++){
if((1 << i) & delta) x = fa[x][i];
}
}
if(x == y){
return x;
}
//Leap to the child node of lca(x,y)
for(int i = LOG - 2;i >= 0;i--){
if(fa[x][i] != fa[y][i]) {
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}
int main(){
scanf("%d%d%d", &n, &m, &r);
for(int i = 1;i < n;i++){
int x,y;
scanf("%d%d", &x, &y);
tree[x].push_back(y);
tree[y].push_back(x);
}
dep[r] = 1;
fa[r][0] = 0;
//Pre-Processing
dfs(r);
for(int i = 1;i <= LOG - 2;i++){
for(int j = 1;j <= n;j++){
fa[j][i] = fa[fa[j][i - 1]][i - 1];
}
}
for(int i = 1;i <= m;i++){
int x,y;
scanf("%d%d", &x, &y);
printf("%d\n", lca(x,y));
}
return 0;
}