最近公共祖先

定义

---

最近公共祖先

最近公共祖先(Lowest Common Ancestor, 简称LCA)，是指在有根树中，对于任意两个节点 $u$ 和 $v$，它们所有公共祖先中距离根节点最远的那个节点（即深度最大的那个祖先）。

性质

---

1. $LCA(u,v)=u$
2. $d(u,v)=d(u)+d(v)-2d(LCA(u,v))$，其中$d(u,v)$为u和v的最短距离，$d(u)$为u到树根的距离

实现

---

朴素算法

对于节点 $u$ 和 $v$ ，进行以下操作

1. 调整 $u$ 和 $v$ 的深度，使两个节点位于同一深度
2. 同时向上移动，直到相遇

倍增算法

通过dfs预处理求出f[u][k]（即u的第$2^k$个祖先），同时求出h[u]（u的深度），d[u]（u到根节点的距离）

int N;
int head[2 * N], nxt[2 * N], v[2 * N], w[2 * N], cnt = -1;  
int f[N][21], h[N], d[N];  
 
void dfs(int u, int father)  
{  
    f[u][0] = father; // 第一个祖先  
    h[u] = h[father] + 1; // 高度 + 1    for (int k = 1; k <= 20; k++)  
       f[u][k] = f[f[u][k - 1]][k - 1]; // 倍增求第2^k个祖先  
    for (int i = head[u]; head[u] != -1; i = next[i]) // 链式前向星遍历出边  
    {  
       if (v[i] == father) // dfs单向  
          continue;  
       d[v[i]] = d[u] + d[i];  
       dfs(v[i], u);  
    }  
}  
  
int lca(int x, int y)  
{  
    if (h[x] > h[y])  
       swap(x, y); // 令x的深度比y小  
    int diff = h[y] - h[x]; // 高度差  
    for (int k = 0; diff != 0; k++)  
    {  
       if ((diff & 1) == 1) // 二进制分解diff  
          x = f[x][k]; // 让x走到和y高度一致  
       diff >>= 1;  
    }  
    if (x == y) // 若为同一节点则直接返回  
       return x;  
    for (int k = 20; k >= 0; k--)  
       if (f[x][k] != f[y][k]) // 在不是同一个点的情况下尽量向上走  
       {  
          x = f[x][k];  
          y = f[y][k];  
       }  
    return f[x][0]; // 返回第一个祖先  
}  
 
int get_d(int x, int y)  
{  
    return d[x] + d[y] - 2 * d[lca(x, y)];  
}