$$最近公共祖先LCA$$

$最近公共祖先$

给定一棵树,若节点z既是x的祖先节点,又是y的祖先节点,那么就称z是x,y的公共祖先

最近公共祖先指的是x,y的公共祖先集合中深度最深的那个点,记为LCA(x,y)

$向上标记法$

$把从x到根节点的路径上所有点标记为1$

$从y向上走到根结点,第一次遇到被标记的点,就找到了LCA(x,y)$

$此算法效率较低,对于每次询问,时间复杂度O(n)$

$向上倍增法$

$对于每个点i,f[i][j]表示i向上走2^j步的点,满足$

$$f[i][j] = f[f[i][j-1]][j-1]$$

$这相当于动态规划的过程,在计算i节点f值时,必须先计算i的所有祖先节点的f值$

$可以用广搜模拟这一过程,在每次入队时预处理f的值$

$在对于每一组x,y在线处理$

$先用倍增把x,y走到同一层$

$再让x,y共同向上走,如果走到了同一个祖先,那么就不走$

$最终x,y再走一步就可以相遇,f[x][0]就是LCA(x,y)$

$对于每次询问,时间复杂度O(log_2^n)$

$总时间复杂度O((n + q)log_2^n)$

$Code$

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = 200010;

int q[N], dep[N], f[N][25];
int h[N], e[M], ne[M], idx;
bool st[N];

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

void bfs(int s)
{
    int hh = 0, tt = 0;
    q[0] = s, st[s] = true;
    dep[s] = 1;

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (st[j])continue;
            st[j] = true;
            q[++ tt] = j;

            f[j][0] = t;
            dep[j] = dep[t] + 1;
            //预处理f[j][k]
            for (int k = 1; k <= 20; k ++ )
                f[j][k] = f[f[j][k - 1]][k - 1];
        }
    }
}

int lca(int x, int y)
{
    if (dep[x] < dep[y])swap(x, y);

    //把较深点向上走到与较浅点同一层
    for (int i = 20; i >= 0; i -- )
        if (dep[f[x][i]] >= dep[y])
            x = f[x][i];

    if (x == y)return x;

    //把x,y同时向上走
    for (int i = 20; i >= 0; i -- )
        if (f[x][i] != f[y][i])
        {
            x = f[x][i];
            y = f[y][i];
        }

    return f[x][0];    
}

int main()
{
    int n, q;
    scanf("%d%d", &n, &q);

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    bfs(1);//广度优先搜索预处理f数组

    while (q -- )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", lca(x, y));
    }

    return 0;
}

$Tarjan算法与LCA$

$Tarjan算法求LCA,这是一个离线算法$

$先按dfs遍历整棵树$

$在搜索点y时,设x在遍历到y之前已经遍历过了$

$而LCA(x,y)一定是x到根节点的路径上的点$

        1
       / \
      /   \
     /     \
    /       \    
   2         3
  / \       / \
 /   \     /   \
4     5   6     7

$现在要求x,y的最近公共祖先$

$以y=7为例$

$1, 3, 7是7到根节点的路径上的点$

$Tarjan算法考虑并查集$

$把(2, 4, 5)加入到以1为祖先的并查集$

$把(6)加入到以3为祖先的并查集$

$遍历到y时,x所在的并查集的祖先就是它们的最近公共祖先$

$时间复杂度为O(n+m)$

$Code$

#include <bits/stdc++.h>

using namespace std;

const int N = 500010, M = 1000010;

int h[N], e[M], ne[M], idx;
vector<int> p[N], id[N];
int q[N], ans[N], f[N];
bool st[N];

int find(int u)
{
    return f[u] != u ? f[u] = find(f[u]) : f[u];
}

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

void tarjan(int u)//dfs
{
    //通过并查集,计算答案
    for (int i = 0; i < p[u].size(); i ++ )
    {
        int j = p[u][i];
        if (!st[j])continue;
        ans[id[u][i]] = find(j);
    }

    st[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (st[j])continue;
        tarjan(j);
        f[j] = u;//搜完后加边
    }
}

int main()
{
    int n, q, s;
    scanf("%d%d%d", &n, &q, &s);

    for (int i = 1; i <= n; i ++ )f[i] = i;

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    for (int i = 1; i <= q; i ++ )
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x == y)ans[i] = x;
        else
        {
            p[x].push_back(y), p[y].push_back(x);
            id[x].push_back(i), id[y].push_back(i);  
        }
    }

    tarjan(s);

    for (int i = 1; i <= q; i ++ )
        printf("%d\n", ans[i]);

    return 0;
}