最近公共祖先算法详解 + 模板题 建议新手收藏 信息学奥赛一本通 祖孙询问

首先什么是最近公共祖先？？

如图：红色节点的祖先为红色的1， 2， 3. 绿色节点的祖先为绿色的1， 2， 3， 4. 他们的最近公共祖先即他们最先相交的地方，如在上图中黄色的点就是他们的最近公共祖先。

求公共祖先的方法：

方法一：向上标记法；时间复杂度O（n）;（不常用）

步骤：以下图为例，先从红色的节点开始遍历到根节点，每次走过的节点记录下来，然后再从绿色的节点开始遍历当第一次遇到红色节点走过的节点时，该节点即为红绿节点的最近公共祖先

 

方法二：

倍增法：时间复杂度 ：预处理 O（nlogn）+ 查询（logn）;

先假设depth[i]为节点 i 的深度，令根节点的深度为1. fa[i][j]为从 i 这个点往上跳2^j步所能走到的节点。

如图：depth[1] = 1; 

以节点6为例子：depth[6] = 4, fa[6][0] = 5, fa[6][1] = 2.

问题：如何求fa

首先fa[i][j]为从点 i 跳 2^j 步所跳到的点。我们可以把它分为，先跳2^j - 1, 再跳2^j - 1即

fa[i][j] = fa[f[ia][j - 1], [j - 1]]。  

步骤。

步骤1：先将两个点同时跳到同一层，若此时a == b则说明此时跳到的这个点即为他们的最近公共祖先

如图假设要求2， 6的最近公共祖先。则当6跳到和2同一层时，此时2或6所在的节点就是他们的最近公共祖先 

步骤2:  让两个点同时往上跳直到跳到他们的最近公共祖先的下一层

问题：为什么是下一层？？

如果直接跳到他们的祖先处的判断不了是否是最近公共祖先

如图：

 假设要求6和5的最近公共祖先，我们先让他们跳到同一层，即节点6跳到节点4. 当他们在同一层时若直接跳到他们共同的祖先则无法判断最后跳到的是节点1还是节点2

倍增：例题

#include 
#include 
#include 
#include 
 
using namespace std;
 
const int N = 40010, M = 2 * N;
 
int n, m;
int depth[N];//表示节点N所在的深度
int fa[N][16];//2^15步大于题目所给的4 * 10^4。
int h[N], e[M], ne[M], idx;
 
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}
 
void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);
    depth[0] = 0;//边界，lca中会说明好处
    depth[root] = 1;//令根节点的层数为1
    
    queue<int> q;
    q.push(root);
    
    while (q.size())
    {
        int t = q.front();
        q.pop();
        
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (depth[j] > depth[t] + 1)
            {
                q.push(j);
                depth[j] = depth[t] + 1;
                fa[j][0] = t;//j往上跳2^0是t
                
                for (int k = 1; k <= 15; k ++ )//2^15超过2 * 10^4
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];//将2^k步分解为跳两次2^k-1, 
                
            }
        }
    }
}
 
int lca(int a, int b)
{
    if (a == b) return 0;//说明他们时同一个节点，谁也不是谁的祖先
    if (depth[a] < depth[b]) swap(a, b);//保证a的深度比b的深度深
    
    for (int k = 15; k >= 0; k -- )
        if (depth[fa[a][k]] >= depth[b])//将a跳到与b同一层, 这里可以看出当fa[a][k]跳出根节点时fa[a][k]即为0，
                                        //所以depth[fa[a][k]]即为0，
                                        //又因为depth[b]大于0所以当跳出去的时候等式不可能成立
            a = fa[a][k];//将a跳到fa[a][k]的位置
    
    if (a == b) return a;//如步骤1的图返回a或b其中一个即可
    //下面步骤说明他们跳到了同一层且a != b;
    for (int k = 15; k >= 0; k -- )//同时往上跳直到跳到最近公共祖先的下一层
        if (fa[a][k] != fa[b][k])//若跳出去了找到的不是最近公共祖先而是其他的祖先
        {                        //则fa[a][k] == fa[b][k]不满足条件，所以他们一定是跳到最近公共祖先
            a = fa[a][k];        //的下一层
            b = fa[b][k];
        }
    
    return fa[a][0];//最后跳到的是最近公共祖先的下一层，所以要在往上跳一层这里填a, b都可
}
 
int main()
{
    cin >> n;
    
    memset(h, -1, sizeof h);
    
    int root;//记录根节点
    while (n -- )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        if (b == -1) root = a;
        add(a, b), add(b, a);//无向边
    }
    
    bfs(root);//预处理depth，与 fa数组
    
    cin >> m;
    while (m -- )
    {
        int a, b;
        scanf("%d %d", &a, &b);
        int p = lca(a, b);//求a, b的最近公共祖先
        if (p == a) puts("1");
        else if (p == b) puts("2");
        else puts("0");
    }
    
    return 0;
}

 

 方法三：tarjan算法：时间复杂度O（n + m）n为节点数量，m为询问数量

tarjan算法是离线算法：何为离线算法？？？

离线算法：将所有询问先保存下来，再完成算法的过程中将结果算出，然后将结果统一输出

在线算法：每次读入一个询问就计算出答案再读如下一个询问，以此类推

步骤：

步骤一： 先将所有节点分为三类。如图中三种颜色圈起来的点

 

 绿色圈里的点表示遍历过且回溯过的点，红色圈里的点表示正在遍历过的点，紫色圈里的点表示还未遍历过的点

步骤二：我们可以把绿色圈遍历后且回溯的时候将他们的根节点与他们本身压缩成一个点，即将12和他的根节点6压缩成一个根节点，将6，12，13和他们的根节点3压缩成一个节点，即使用并查集的方法缩点。

步骤三：要求x, y的最近公共祖先，即从y开始遍历第一次碰到的绿色圈的的点，那个点就是最近公共祖先

若是还没有理解看以下例题好理解很多

 例题：

给出 n 个点的一棵树，多次询问两点之间的最短距离。

注意：

• 边是无向的。
• 所有节点的编号是 1,2,…,n。

输入格式

第一行为两个整数 n 和 m。n 表示点数，m 表示询问次数；

下来 n−1 行，每行三个整数 x,kx,y,k，表示点 x 和点 y 之间存在一条边长度为 k；

再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。

树中结点编号从 1 到 n。

输出格式

共 mm 行，对于每次询问，输出一行询问结果。

数据范围

2≤n≤104,
1≤m≤2×104,
0 1≤x,y≤n

输入样例1：

2 2 
1 2 100 
1 2 
2 1

输出样例1：

100
100

输入样例2：

3 2
1 2 10
3 1 15
1 2
3 2

输出样例2：

10
25

难度：中等

时/空限制：1s / 64MB

总通过数：6074

总尝试数：12757

来源：《信息学奥赛一本通》

算法标签

如何求两点之间的距离？？ 

 

如图，我们可以预处理一个从任意节点到根节点的距离 即图中dist[x]表示x到根节点距离,dist[y]表示y到根节点距离，anc为他们的最近公共祖先，则x, y直接的距离为:

dist[x] + dist[y] - 2 * dist[anc];

#include 
#include 
#include 
#include 
 
#define x first
#define y second
 
using namespace std;
 
const int N = 10010, M = N * 2;
 
typedef pair<int, int> PII;
 
int n, m;
int p[N];//p[i]表示i的父节点为p[i]
int st[N];//判断该点的类型
int res[M];//存的是答案
int dist[N];//某个点到根节点的距离
vector query[N];//query[a] = {b, id},其中a, b指的是要求的最近公共祖先，id表示他们的编号
int h[N], e[M], ne[M], w[M], idx;//邻接表数组
 
void add(int a, int b, int c)//邻接表
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
    idx ++ ;
}
 
int find(int x)//并查集
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
 
void dfs(int u, int fa)//寻找某个点到根节点的距离
{
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (j != fa)//若没有往回搜
        {
            dist[j] = dist[u] + w[i];
            dfs(j, u);
        }
    }
}
 
void tarjan(int u)
{
    st[u] = 1;//正在遍历u点
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            tarjan(j);
            p[j] = u;//这是正在回溯，将j和他的父节点压缩成一个点
        }
    }
    
    //回溯完成这里可以直接写st[u] = 2;但为了更好的理解我们写在最后
    
    for (auto item : query[u])//这里一定能搜到因为我们存了两个方向的边
    {                         //因此一定有一种情况是st[y] == 2而u正在遍历
        int y = item.x, id = item.y;
        if (st[y] == 2)
        {
            int anc = find(y);
            res[id] = dist[u] + dist[y] - 2 * dist[anc];
        }
    }
    
    st[u] = 2;//回溯完成后将u表示为绿色圈的部分
}
 
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i;//初始化
    
    memset(h, -1, sizeof h);
    
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    
    for (int i = 0; i < m; i ++ )//读入询问
    {
        int a, b;
        scanf("%d %d", &a, &b);
        query[a].push_back({b, i});
        query[b].push_back({a, i});
    }
    
    dfs(1, -1);//随便以一个点为根节点，这里我们是以1为根节点
    tarjan(1);
    
    for (int i = 0; i < m; i ++ ) printf("%d\n", res[i]);//按顺序输出答案
    
    return 0;
}