526互联

Template <lca 最近公共祖先>

发布时间 2023-08-03 10:59:52作者: O2iginal

01 倍增lca

P3379 【模板】最近公共祖先（LCA） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1.1 常用简短版本（利用结点深度)

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
const int N = 5e5 + 10;

vector<int> adj[N];         // 邻接点
int dep[N];                 // 结点深度
int up[N][20], lim = 20;    // 结点i的向上第2^j个祖先，lim为j的最大值(根据输入的结点个数n计算)

// 获得 up[][] 和 dep[]
void dfs(int u, int p)
{
    dep[u] = dep[p] + 1;

    up[u][0] = p;
    for (int i = 1; i <= lim; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];

    for (auto v : adj[u])
    {
        if (v == p)
            continue;
        dfs(v, u);
    }
}

// 倍增 求 lca
int lca(int u, int v)
{
    // 使u的深度大于等于v的深度
    if (dep[u] < dep[v]) swap(u, v);
    // u向上跳，直到与v深度相同
    for (int i = lim; i >= 0; i--) if (dep[up[u][i]] >= dep[v]) u = up[u][i];
    // 判断此时u是否已经跳到v
    if (u == v) return u;
    // u和v已经深度相同，一起向上跳，始终保持深度相同，则能跳到lca的字节点处
    for (int i = lim; i >= 0; i--)
        if (up[u][i] != up[v][i])
        {
            u = up[u][i];
            v = up[v][i];
        }
    return up[u][0];
}

void solv()
{
    int n, q, root = 1;  // 结点数，询问数，根节点序号
    cin >> n >> q >> root;
    lim = ceil(log2(n));
    for (int i = 1; i <= n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dfs(root, 0);
    
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solv();
    }
    return 0;
}

1.2 利用dfs序判断祖先版本

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
const int N = 5e5 + 10;

vector<int> adj[N];         // 邻接点
int up[N][20], lim = 20;    // 结点i的向上第2^j个祖先，lim为j的最大值(根据输入的结点个数n计算)
int tml[N], tmr[N], timer;  // dfs进入结点i子树时序号，离开结点i子树时序号，dfs访问计数timer

// 获得 up[][] 和 tml[] tmr[]
void dfs(int u, int p)
{
    tml[u] = ++ timer;

    up[u][0] = p;
    for (int i = 1; i <= lim; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];

    for (auto v : adj[u])
    {
        if (v == p) continue;
        dfs(v, u);
    }
    tmr[u] = ++ timer;
}

// p 是否为 u 的祖先
bool check(int p, int u)
{
    return tml[p] <= tml[u] and tmr[p] >= tmr[u];
}

// 倍增 求 lca
int lca(int u, int v)
{
    // 判断u v间是否已经是祖先关系
    if (check(u, v)) return u;
    if (check(v, u)) return v;
    // u结点向上跳，这样保证一定是u的祖先，通过check判断是否为v的祖先
    for (int i = lim; i >= 0; i --) 
        if (!check(up[u][i], v)) 
            u = up[u][i];
    return up[u][0];
}

void solv()
{
    int n, q, root = 1;  // 结点数，询问数，根节点序号
    cin >> n >> q >> root;
    lim = ceil(log2(n));
    for (int i = 1; i <= n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    // 注意这里dfs传入root的父节点为0号结点，因而需要对tmr赋无穷大（ 或直接写成dfs(root,root) ）
    tml[0] = 0, tmr[0] = 1e9;
    dfs(root, 0);

    while (q--)
    {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
    {
        solv();
    }
    return 0;
}