倍增（lca模板）

http://poj.org/problem?id=1330

题意：给出一颗n个节点的树，问u、v的lca。

解法：倍增：

1、两数组fa[i][j]表示i节点的长为2^j的祖先，de[u]记录节点深度。

2、dfs遍历预处理de[u] , 有fa[u][i] = fa[fa[u][i-1]][i-1] 表示u节点的长为2ⁱ的祖先为，u节点长为2^i-1的祖先的长为2^i-1的祖先。

3、在线询问：lca（u，v）：

4、先将深度大的点向上以2的幂次长向上跳，根据整数分解（或则二进制）性质可知，深度大的点会慢慢逼近深度小的点并最终位于同一深度。

5、此时特判u、v是否重合，重合即v为lca。

6、否则两点同时往上跳，根据性质可知一定可以跳到u、v的lca的下一节点，所以fa[u][0]表示u的父节点即为lca。

疑问：为什么一定可以跳到lca的下一节点呢？

比如两节点此时在同一深度，距离lca长度为4，二进制表示为100，这两点同时跳2，再跳1.就达到目的。

根据二进制性质可知相差任意距离都可以达到目的。

疑问：为什么不直接逃到 fa[u][i] == fa[v][j] 这个点呢？

因为跳到的这个点不一定是最近的公共祖先.

注意：数组fa也要初始化。

思路：倍增是在朴素算法上的一个优化，朴素算法就是两个结点一步一步跳，而倍增是利用二进制性质一大步一大步跳，而一大步一大步跳就需要知道跳到了哪个结点

所以需处理出fa[i][j]表示i结点往上跳2的j次方步到达的结点。

https://blog.csdn.net/Q_M_X_D_D_/article/details/89924963

#include<bits/stdc++.h>
using namespace std ;
const int N = 40010 , M = 80010 ;
int fa[N][30] , n , q , dep[N] ;
int e[M] , ne[M] , h[N] , idx;

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

void dfs(int u , int pre){//0作为一个虚根
    dep[u] = dep[pre] + 1 ;
    fa[u][0] = pre;
    for(int i = 1 ; (1 << i) <= dep[u] ; i++){//最多跳到虚根
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for(int i = h[u] ; ~i ; i = ne[i]){
        int j = e[i] ;
        if(j == pre) continue;
        dfs(j , u);
    }
}

int lca(int a , int b){
    if(dep[a] < dep[b]) swap(a , b);
    for(int i = 20 ; i >= 0 ; i--){//跳到同一深度
        if(dep[a] - (1 << i) >= dep[b]){
            a = fa[a][i];
        }
    }
    if(a == b) return a ;
    for(int i = 20 ; i >= 0 ; i --){//跳到最近公共祖先
        if(fa[a][i] != fa[b][i]){
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];
}
int main(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("D:\\c++\\in.txt", "r", stdin);
        //freopen("D:\\c++\\out.txt", "w", stdout);
    #endif
    memset(h , -1 , sizeof(h));
    cin >> n ;
    int rt ;
    for(int i = 1 ; i <= n ; i++){
        int a , b ;
        cin >> a >> b ;
        if(b == -1){
            rt = a ;
            continue;
        }
        add(a , b);
        add(b , a);
    }
    dfs(rt , 0);
    cin >> q;
    for(int i = 1 ; i <= q ; i++){
        int a , b ;
        cin >> a >> b ;
        cout << lca(a ,b) << endl;
    }
}

原文链接: https://www.cnblogs.com/nonames/p/12329549.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/330513

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

倍增（lca模板）

相关推荐