历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

最近公共祖先LCA 复习笔记

作者：

真我Elysia , 2022-07-26 19:35:39 , 所有人可见 , 阅读 202

1

1

最近公共祖先LCA

参考资料：
算法提高课，算法竞赛进阶指南。

向上标记法On

通过一个点向上走，标记跟他在同一条路径上的点。再另外一个点向上走，遇到的第一个点就是他们的最近公共祖先。

倍增法

fa[i,j]从i开始向上走2^j步能到达的节点。
除此之外，fa[x,k] = fa[ fa[x,k-1] , k-1 ]
depth[i]表示i的深度

哨兵：如果从i开始向上走2^j步会跳过根节点，namofa[i,j] = 0，depth[0] = 0。

简短的思路：

先将两个点跳到同一层。
让两个点同时往上跳，一直跳到他们的最近公共祖先的下一层（跳到最近公共祖先的儿子）。

求LCA(x,y)的步骤：

设depth[x] >= depth[y]。
采用二进制拆分思想，把x向上调整到和y同一深度。

依次尝试从x向上走 $k = 2^{logn} , \cdots , 2^1 , 2^0$ 步，检查到达的节点是否比y深。在每次检查中，若是，则令x = fa[x,k]。
若此时x = y，则说明找到LCA。LCA = y。

这是当x和y在同一条路径中的情况。
用二进制的思想，将x和y向上同时调整，并保持深度一致且二者不相会。

具体来说就是把x,y同时向上走 $k = 2^{logn} , \cdots , 2^1 , 2^0$ 步。在每次尝试中，若fa[x,k] != fa[y,k] ，则令x = fa[x,k] , y = fa[y,k]。
此时x,y差一步相会，他们的父亲节点fa[x,0]就是LCA。

预处理O(nlogn)

查询O(logn)

倍增法

模板题

https://www.acwing.com/activity/content/problem/content/1537/
火狐截图_2022-07-26T02-51-09.937Z.png

刚开始听Y总讲解代码思路时，还是有点不清晰。
看了大佬的详细解释后才清晰，这里引用下大佬对代码的解释
大佬的博客

int t,root;
int n,idx;
int depth[N],fa[M][16];
int h[N],e[N],ne[N];

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

void bfs( int root )
{
    memset( depth , 0x3f , sizeof depth );
    depth[0] = 0 , depth[root] = 1;
    queue< int > q;
    q.push( root );
    while( q.size() )
    {
        int t = q.front();
        q.pop();
        for( int i = h[t] ; ~i ; i = ne[i] )
        {
            int j = e[i];
            // j没有被找到过
            if( depth[j] > depth[t]+1 )
            {
                depth[j] = depth[t]+1;
                q.push(j);
                fa[j][0] = t;
                //j往上跳2^0步后就是t
                /*
                i  →  mid  →  t
                  2^j-1  2^j-1
                  f[i][j-1] f[i][j]
                mid = f[i][j-1]  
                t = f[i][j]
                则f[i][j] = f[mid][j-1] = f[f[i][j-1]][j-1]
                */
                for(int k=1;k<=15;k++)
                {
                    fa[j][k] = fa[fa[j][k-1]][k-1];
                }
                /*
                举个例子理解超过根节点是怎么超过的
                因为我们没有对根节点fa[1][0]赋值,那么fa[1][0] = 0;
                    1
                   / \
                  2   3 
                fa[1][0] = 0;
                fa[2][0] = 1;
                fa[2][1] = fa[fa[2][0]][0] = fa[1][0] = 0;
                */
            }
        }
    } 
}

int lca(int a, int b)
{
    // 为方便处理 当a在b上面时 把a b 互换  
    if (depth[a] < depth[b]) swap(a, b);
    //把深度更深的a往上跳到b
    for (int k = 15; k >= 0; k -- )
        //当a跳完2^k依然在b下面 我们就一直跳
        //二进制拼凑法
        //这里因为
        if (depth[fa[a][k]] >= depth[b])
            a = fa[a][k];
    //如果跳到了b
    if (a == b) return a;
    //a,b同层但不同节点
    for (int k = 15; k >= 0; k -- )
        // 假如a,b都跳出根节点,fa[a][k]==fa[b][k]==0 不符合更新条件
        if (fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    //循环结束 到达lca下一层
    //lca(a,b) = 再往上跳1步即可
    return fa[a][0];
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d",&n);
    for( int i = 1 ; i <= n ; i++ )
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if( b == -1 ) root = a;
        else add( a , b ) , add( b , a );
    }

    bfs( root );

    scanf("%d",&t);
    while( t-- )
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int ans = lca(x,y);
        if( ans == x ) puts("1");
        else if( ans == y ) puts("2");
        else puts("0");
    }
    return 0;
}

LCA的Tarjan算法

Tarjan为离线的LCA算法。

算法中的离线，在线做法的概念：
离线就是把题目的询问全部存下来，然后一次性进行输出。
在线就是题目每询问一次就回答一次。

Tarjan是使用并查集对向上标记法的优化。

我们将树上的节点分为3种。

已经访问完并回溯完毕的点。在这些点标记为整数2.
已经开始递归，但未完成回溯的点。这些节点就是当前正在访问的节点x以及x的祖宗。这些标记为整数1。
尚未访问的点。这些节点没有标记也就是整数0。

模板题

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

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

输入格式:
第一行为两个整数 n 和 m。
n 表示点数，m 表示询问次数；
接下来 n−1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；
再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。
树中结点编号从 1 到 n 。

输出格式：
共 m 行，对于每次询问，输出一行询问结果。

https://www.acwing.com/activity/content/problem/content/1538/

代码的解释参考了大佬的博客
orz

int n,m,idx;
int p[M];
int st[M];
int ans[M];
int dist[M*2];
int h[M*2],ne[M*2],e[M*2],w[M*2];

vector<PII>query[M];

void add( int u , int v , int val ) 
{
    e[idx] = v , w[idx] = val , ne[idx] = h[u] , h[u] = 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 ; i = ne[i] )
    {
        int j = e[i];
        if( j == fa ) continue;
        dist[j] = dist[u]+w[i];
        dfs( j , u );
    }
}

void tarjan( int u )
{   
    // 当前搜索的节点标记为1
    st[u] = 1;
    for( int i = h[u] ; ~i ; i = ne[i] )
    {
        int j = e[i];
        if( st[j] ) continue;
        tarjan( j );
        p[j] = u;
    }

    // 搜索所有和u建边的节点
    for( auto item : query[u] )
    {
        int y = item.first;
        int id = item.second;
        if( st[y] == 2 )
        {
        //如果查询的这个点已经是左下的点(已经搜索过且回溯过,标记为2)
            int anc = find(y);
            // x到y的距离 = d[x]+d[y] - 2*d[lca] 
            ans[id] = dist[u] + dist[y] - dist[anc]*2;
        }
    }

    // 访问完并回溯完的节点标记为2
    st[u] = 2;
}

int main(){

    scanf("%d%d",&n,&m);
    memset( h , -1 , sizeof h );
    for( int i = 1 ; i <= n-1 ; i++ )
    {
        int a,b,val;
        scanf("%d%d%d",&a,&b,&val);
        add( a , b , val );
        add( b , a , val );
    }
    for( int i = 1 ; i <= m ; i++ )
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if( a == b ) continue;
        query[a].push_back( {b,i} );
        query[b].push_back( {a,i} );
    }

    // 因为使用了并查集进行优化，所以要进行初始化。
    for( int i = 1 ; i <= n ; i++ ) p[i] = i;

    // 预处理一遍所有边到根节点的距离。
    dfs( 1 , -1 );
    // 从1点开始进行taijan
    tarjan( 1 );

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

    return 0;
}