当前位置：网站首页>倍增 LCA（最近公共祖先）

倍增 LCA（最近公共祖先）

2022-07-02 09:42:00 【蛀牙牙乐】

倍增：

把n倍大模拟拆成 ${log_{2}}^{n}$ 模拟（可以这么理解），之所以用2是由于2的次方可以凑出所有正整数

环问题（https://oi-wiki.org/basic/binary-lifting/）：这里只对倍增法解释

它的思想就是求出x + k这一圈的值，再将m次拆为 ${log_{2}}^{m}$ 次得到答案。有结论：最多n次循环可回到原点，所以每个循环必定不重不漏。

题单： https://www.luogu.com.cn/training/203#problems

LCA：

树中两个结点共同的祖先（往上找可以找到最近的两个点同时能到达的祖先结点）

一些性质： https://oi-wiki.org/graph/lca/

暴力：

dfs一层一层找

学长的板子，大概是这么个理

void dfs(int u, int fa)
    father[u] = fa;
    deep[u] = deep[fa] + 1;
    for (int i = head[u]; ~i; i = edge[i].pre){
        int v = edge[i].to;
        if(v != fa)
            dfs(v, u);
    }
}

int lca1(int u, int v){
    while(u != v){
        if(deep[u] < deep[v]){
            swap(u, v);
        }
        u = father[u];
    }
    return u;
}

int lca2(int u, int v){
    if(deep[u] < deep[v]){
        swap(u, v);
    }
    while(deep[u] > deep[v]){
        u = father[u];
    }
    while(u != v){
        u = father[u];
        v = father[v];
    }
    return u;
}

倍增LCA：

预处理x的 $2^{i}$ 祖先（每次跳 $2^{i}$ ）+ 拆分两节点高度差

P3379 【模板】最近公共祖先（LCA）(https://www.luogu.com.cn/problem/P3379)

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int maxn = 5e5 + 5;
const int DEG = 30;
#define re(a) memset(a, -1, sizeof(a))

struct Edge{
    int to, next;
}edge[maxn * 2];

int head[maxn], tot;

void addedge(int u, int v){
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void init(){
    tot = 0;
    re(head);
}

int fa[maxn][DEG], deg[maxn];

void bfs(int root){
    queue<int> que;
    deg[root] = 0;
    fa[root][0] = root;
    que.push(root);
    while(!que.empty()){
        int tmp = que.front();
        que.pop();
        for(int i = 1; i < DEG; ++i){
            fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1];
        }
        for (int i = head[tmp]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(v == fa[tmp][0])
                continue;
            deg[v] = deg[tmp] + 1;
            fa[v][0] = tmp;
            que.push(v);
        }
    }
}

int lca(int u, int v){
    if(deg[u] > deg[v]){
        swap(u, v);
    }
    int hu = deg[u], hv = deg[v];
    int tu = u, tv = v;
    for (int det = hv - hu, i = 0; det; det >>= 1, ++i){
        if(det & 1)
            tv = fa[tv][i];
    }
    if(tu == tv)
        return tu;
    for(int i = DEG - 1; i >= 0; --i){
        if(fa[tu][i] == fa[tv][i]){
            continue;
        }
        tu = fa[tu][i];
        tv = fa[tv][i];
    }
    return fa[tu][0];
}
bool flag[maxn];
int main(){
    int n, m, s;
    init();
    memset(flag, false, sizeof(flag));
    cin >> n >> m >> s;
    for (int i = 1; i < n; ++i){
        int a, b;
        cin >> a >> b;
        addedge(a, b);
        addedge(b, a);
        flag[b] = true;
    }
    int root;
    for (int i = 1; i <= n; ++i){
        if(!flag[i]) {
            root = i;
            break;
        }
    }
    bfs(s);//根节点
    for (int i = 0; i < m; ++i){
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
        return 0;
}

题：

Nearest Common Ancestors（https://vjudge.net/problem/POJ-1330）

把上面板子抄下来改改就能过

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;

const int maxn = 5e5 + 5;
const int DEG = 30;
#define re(a) memset(a, -1, sizeof(a))

struct Edge{
    int to, next;
}edge[maxn * 2];

int head[maxn], tot;

void addedge(int u, int v){
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

void init(){
    tot = 0;
    re(head);
}

int fa[maxn][DEG], deg[maxn];

void bfs(int root){
    queue<int> que;
    deg[root] = 0;
    fa[root][0] = root;
    que.push(root);
    while(!que.empty()){
        int tmp = que.front();
        que.pop();
        for(int i = 1; i < DEG; ++i){
            fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1];
        }
        for (int i = head[tmp]; i != -1; i = edge[i].next){
            int v = edge[i].to;
            if(v == fa[tmp][0])
                continue;
            deg[v] = deg[tmp] + 1;
            fa[v][0] = tmp;
            que.push(v);
        }
    }
}

int lca(int u, int v){
    if(deg[u] > deg[v]){
        swap(u, v);
    }
    int hu = deg[u], hv = deg[v];
    int tu = u, tv = v;
    for (int det = hv - hu, i = 0; det; det >>= 1, ++i){
        if(det & 1)
            tv = fa[tv][i];
    }
    if(tu == tv)
        return tu;
    for(int i = DEG - 1; i >= 0; --i){
        if(fa[tu][i] == fa[tv][i]){
            continue;
        }
        tu = fa[tu][i];
        tv = fa[tv][i];
    }
    return fa[tu][0];
}
bool flag[maxn];
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        init();
        memset(flag, false, sizeof(flag));
        cin >> n;
        for (int i = 1; i < n; ++i){
            int a, b;
            cin >> a >> b;
            addedge(a, b);
            addedge(b, a);
            flag[b] = true;
        }
        int root;
        for (int i = 1; i <= n; ++i){
            if(!flag[i]) {
                root = i;
                break;
            }
        }
        bfs(root);//根节点
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
        return 0;
}

错麻了，有机会再补吧

贴一个能过的代码

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
#define re(a) memset(a, 0, sizeof(a))
//other code 
vector<int> adj[maxn], cost[maxn];
int dis[maxn], up[maxn][21], dep[maxn];

void clear(int n){
    for (int i = 1; i <= n; ++i){
        dis[i] = 0;
        adj[i].clear();
        cost[i].clear();
        dep[i] = 0;
        for (int j = 0; j <= 18; ++j)
            up[i][j] = 0;
    }
}

void dfs(int s, int p){
    if(p != -1)
        up[s][0] = p;
    for (int i = 1; i <= 18; ++i)
        up[s][i] = up[up[s][i - 1]][i - 1];
    for (int i = 0; i < adj[s].size(); ++i){
        int v = adj[s][i];
        int d = cost[s][i];
        if(v == p)
            continue;
        dis[v] = dis[s] + d;
        dep[v] = dep[s] + 1;
        dfs(v, s);
    }
}

int lca(int a, int b){
    if(dep[a] > dep[b])
        swap(a, b);
    int d = dep[b] - dep[a];
    for (int i = 18; i >= 0; --i){
        if(d & (1 << i))
            b = up[b][i];
    }
    if (a == b)
        return a;
    for (int i = 18; i >= 0; --i){
        if(up[a][i] != up[b][i]){
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

int main(){
    int t, n;
    cin >> t;
    while(t--){
        cin >> n;
        clear(n);
        // re(dis);
        // re(up);
        // re(dep);
        // adj->clear();
        // cost->clear();
        for (int i = 1; i < n; ++i){
            int a, b, c;
            cin >> a >> b >> c;

            adj[a].push_back(b);
            adj[b].push_back(a);

            cost[a].push_back(c);
            cost[b].push_back(c);
        }
        dfs(1, -1);
        string s;
        while(1){
            cin >> s;
            if(s == "DIST") {
                int a, b;
                cin >> a >> b;
                cout << (dis[a] + dis[b] - 2 * dis[lca(a, b)]) << endl;
            }
            else if(s == "KTH"){
                int a, b, k;
                cin >> a >> b >> k;
                if(k == 1){
                    cout << a << endl;
                    continue;
                }
                int lc = lca(a, b);
                int d = dep[a] - dep[lc];
                if(d + 1 >= k){
                    if(lc == a){
                        if(d + 1 == k) {
                            cout << b << endl;
                            continue;
                        }
                        else
                            k = d + 1 - k + 1;
                    }
                    k--;
                    for(int i = 18; i >= 0; --i){
                        if(k & (1 << i))
                            a = up[a][i];
                    }
                    cout << a << endl;
                }
                else {
                    k -= d;
                    --k;
                    d = dep[b] - dep[lc];
                    k = d - k;
                    for (int i = 18; i >= 0; --i){
                        if(k & (1 << i))
                            b = up[b][i];
                    }
                    cout << b << endl;
                }
            }
            else
                break;
        }
    }
    return 0;
}

原网站

版权声明
本文为[蛀牙牙乐]所创，转载请带上原文链接，感谢
https://blog.csdn.net/m0_50007959/article/details/124991542