题目描述

对于有根树而言，祖先是指从某个结点出发，顺着某条路径往上走到根结点，这条路上经过的所有结点，都是该结点的祖先。若两个结点的祖先相同，则叫该节点的公共祖先。离两个结点最近的公共祖先称为最近公共祖先（Lowest Common Ancestor），简称LCA。

两个点的LCA只有一个，且一定是两个点到根的路径中重复部分最下端的点。

算法1

两个结点逐步向根结点移动。需要预处理求出以下信息：

1. 每个结点的深度depth[i]
2. 每个结点的父结点fa[i]

算法思想：

如果两个结点不相同，就将较深的结点向上移动，直到移动到相同结点，那么该结点即为公共祖先结点。

时间复杂度

$O(n * m)$

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 40010, M = 2 * N;

int h[N], e[M], ne[M], idx;
int depth[N], fa[N];

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

//预处理每个结点的深度，以及结点的父结点的编号
void dfs(int u, int father)
{
    depth[u] = depth[father] + 1;
    fa[u] = father;

    for(int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if(v != father) dfs(v, u);
    }
}

//求u和v的公共祖先
int getlca(int u, int v)
{
    //只要u和v不同
    while(u != v)
    {
        //将深度大的结点向上移动
        if(depth[u] < depth[v]) v = fa[v];
        else u = fa[u];
    }
    return u;
}

int main()
{
    int n, m, root;
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 0; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        if(b != -1)  add(a, b), add(b, a);
        else root = a;
    }

    //预处理，求每个结点的深度与父结点
    dfs(root, 0);

    cin >> m;

    while(m --)
    {
        int a, b;
        cin >> a >> b;

        int lca = getlca(a, b);

        if(a == lca) puts("1");
        else if(b == lca) puts("2");
        else puts("0");
    }

    return 0;
}

算法2

(倍增法) $O(nlogn)$

倍增法求LCA，是对算法1中一步步移动的改进，核心是让两个结点每次向上走的步数为2的次幂。
需要预处理求出以下信息：

1. fa[i, j]表示从结点i开始，向上走$2^j$步所能达到的结点，其中$0<=j<=logn$。
2. depth[i]表示结点i的深度

算法思想：

1. 先将两个结点跳到相同深度
2. 让两个结点同时往上调，一直跳到它们的最近公共祖先下面的一层。

时间复杂度 $O(nlogn)$

预处理：$O(nlogn)$
查询：$O(logn)$

参考文献

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 40010, M = 2 * N;

int h[N], e[M], ne[M], idx;

//fa[i][j]表示从结点i跳2^k后达到的结点编号，0<=j<=log40000≈15
int depth[N], f[N][16];
int q[N];

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

//dfs预处理depth[i], fa[i][j]
void dfs(int u, int father)
{
    depth[u] = depth[father] + 1;
    f[u][0] = father;

    for(int i = 1; i <= 15; i ++) f[u][i] = f[f[u][i - 1]][i - 1];

    for(int i = h[u]; ~i; i = ne[i])
    {
        int v = e[i];
        if(v != father) dfs(v, u);
    }
}

//bfs预处理depth[i], fa[i][j]
void bfs(int root)
{
    memset(depth, 0x3f, sizeof depth);

    //结点0作为哨兵，用来处理越界情况
    //跟结点的深度为1
    depth[0] = 0, depth[root] = 1;

    int hh = 0, tt = 0;
    q[tt] = root;

    while(hh <= tt)
    {
        int u = q[hh++];

        for(int i = h[u]; ~i; i = ne[i])
        {
            int v = e[i];

            //如果v点的深度 > u点的深度 + 1
            if(depth[v] > depth[u] + 1)
            {
                depth[v] = depth[u] + 1;
                q[++tt] = v;
                //从v点跳一步走到u
                f[v][0] = u;
                //求f[v][1...15]
                for(int j = 1; j <= 15; j++)
                    f[v][j] = f[f[v][j - 1]][j - 1];
            }
        }
    }
}


//求u和v的公共祖先
int getlca(int u, int v)
{
    //将u设置为较深结点
    if(depth[u] < depth[v]) swap(u, v);

    //将u向上跳，直到跳到同一层
    for(int i = 15; i >= 0; i --)
    {
        //如果f[u][j]跳出了根结点（值为0），由于设置了哨兵depth[0] = 0，所以不会将u向上跳
        if(depth[f[u][i]] >= depth[v])
            u = f[u][i];
    }

    if(u == v) return u;

    //将u和v同时向上跳，直到跳到最近公共祖先的下一层
    for(int i = 15; i >= 0; i --)
    {
        //如果u和v都跳出了根结点，由于设置了哨兵depth[0] = 0，值同时为0，循环结束
        if(f[u][i] != f[v][i])
        {
            u = f[u][i], v = f[v][i];
        }
    }

    //注意：最后返回的公共祖先为f[u][0]
    return f[u][0];

}

int main()
{
    int n, m, root;
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 0; i < n; i ++)
    {
        int a, b;
        cin >> a >> b;
        if(b != -1)  add(a, b), add(b, a);
        else root = a;
    }

    //bfs预处理
    bfs(root);
    //dfs预处理
    //dfs(root, 0);

    cin >> m;

    while(m --)
    {
        int a, b;
        cin >> a >> b;

        int lca = getlca(a, b);

        if(a == lca) puts("1");
        else if(b == lca) puts("2");
        else puts("0");
    }

    return 0;
}