02 最近公共祖先（LCA）树上倍增法（附代码实现模板）

最近公共祖先（LCA） 最近公共祖先解决的问题

给定一颗有根树，若节点z即是节点x的祖先，也是节点y的祖先，则称z是x，y的公共祖先。

在x，y的所有公共祖先中，深度最大（距离根节点的距离最远的）的一个称为x，y的最近公共祖先，记作LCA(x,y)。

LCA(x,y)是x到根的路径与y到根的路径的交会点。

它也是x与y之间的路径上深度最小的节点。

求最近公共祖先的方法通常有以下三种。

方法1 向上标记法

从 x 向上走到根节点，并标记所有经过的节点。

从y向上从到根节点，当第一次遇到已经标记的节点时，就找到了LCA（x,y）。

对于每个询问，向上标记法的时间复杂度最坏是O（n）。

方法2 树上倍增法

树上倍增法是一个很重要的算法。

除了求LCA之外，它在很多问题中都有广泛的应用。

设F[x,k]表示x的 2^k 辈祖先，即从 x 向根节点走 2^k 步到达的节点。

特别地，若该节点不存在，则令 F[x,y] = 0。

F[x,0] 就是x节点的父节点。

除此之外，任意的 k 属于 [1,log n],F[x,k] = F[F[x,k-1],k-1]。

这类似一个动态规划的过程，“阶段” 就是节点的深度。

因此，我们可以对树进行广度优先遍历，按照层次顺序，在节点入队之前，计算它在F数组中相应的值。

以上部分是预处理，时间复杂度为O（n log n） ，之后可以多次对不同的x，y计算LCA，每次询问的时间复杂度为O（log n）。

基于 F 数组计算LCA（x，y）分为以下几步。

1. 设 d[x] 表示 x的深度。
   

   
   

   设 d[x] >= d[y] (否则可交换x，y)。
   

   
   

2. 用二进制拆分思想，把 x 向上调整到与 y 同一深度。
   

   
   

   具体来说就是依次尝试从 x 向上走k = 2 ^logn,…,2 ¹,2⁰步，检查到达的节点是否比y深。
   

   
   

   在每次检查中，若是，则令 x = F[x,k]。
   

   
   

3. 若此时 x == y ,说明已经找到了LCA，LCA就等于y。
   

   
   

   就是y是x的父节点这种情况。
   

   
   

4. 用二进制拆分思想，把x，y同时向上走k = 2 ^logn,…,2 ¹,2⁰步，在每次尝试中，若F[x,k] != F[y,k] (还没找到共同父节点)，则令 x = F[x,k],y= F[y,k]。
   

   
   

   继续往上面找。
   

   
   

5. 此时x，y必定只差一步就相会了，他们的父节点F[x,0] 就是LCA。
   

   
   

具体样例图解

具体代码实现

洛谷题目 p3379

#include 
#include 
#include 
#include 
#include 


using namespace std;

const int N = 5e5+10;
int h[N],e[N*2],ne[N*2],idx;
int f[N][21];
int d[N];
int n,m,root;

void add(int a,int b) // 存边
{ 
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

void bfs(int u)  /// 预处理
{
    queue<int> q; q.push(u),d[u] = 1;
    while(!q.empty())
    {
        int x = q.front(); q.pop();
        for(int i=h[x]; ~i; i = ne[i])
        {
            int y = e[i];
            if(d[y]) continue;          // 已经更新过的点 不需要在更新了
            d[y] = d[x]+1;
            f[y][0] = x; 
            for(int j = 1; j<=20; j++)  // 这里懒了 没有写log判断树的最高高度
                f[y][j] = f[f[y][j-1]][j-1];
            q.push(y);                  // 把当前点放入 队列中
        }
        
    }
}

int lca(int a,int b)
{
    if(d[a]<d[b]) swap(a,b);
    for(int i=20; i>=0; i--)
        if(d[f[a][i]]>=d[b])  // 找到和b同高度的节点
            a = f[a][i];
    if(a==b) return a;
    for(int i=20; i>=0; i--)
        if(f[a][i]!=f[b][i]) a= f[a][i],b = f[b][i]; // 往上找有共同的根的位置
    
    return f[a][0];
}


int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    memset(h, -1, sizeof h);  // 初始化头节点
    cin>>n>>m>>root;
    for(int i=1; i<n; i++)
    {
        int a,b; cin>>a>>b;
        add(a,b); add(b,a);   //双向边
    }
    bfs(root);
    
    while (m -- )
    {
        int a,b; cin>>a>>b;
        cout<<lca(a,b)<<"\n";
        
    }
    
    return 0;
}