最近公共祖先 - 百科

朴素

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int n, m, s; // 点数、询问数、起点
vector<int> e[MAXN + 5];
namespace work1
{
int fa[MAXN + 5];
int dep[MAXN + 5];
void dfs(int u, int father)
{
    fa[u] = father;
    dep[u] = dep[father] + 1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == father)
            continue;
        dfs(v, u);
    }
}
bool vis[MAXN + 5];
int lca(int u, int v)
{
    if (dep[u] > dep[v])
        swap(u, v);
    while (dep[u] != dep[v])
        v = fa[v];
    while (u != v)
        u = fa[u], v = fa[v];
    return u;
}
void main()
{
    dfs(s, 0);
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
}
} // namespace work1
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    work1::main();
    return 0;
}

倍增

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
const int LOGN = 20;
int n, m, s; // 点数、询问数、起点
vector<int> e[MAXN + 5];
int f[MAXN + 5][LOGN + 5];
int dep[MAXN + 5];
void dfs(int u, int fa)
{
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfs(v, u);
    }
}
bool vis[MAXN + 5];
int lca(int u, int v)
{
    if (dep[u] > dep[v])
        swap(u, v);
    for (int i = LOGN; i >= 0; i--)
        if ((1 << i) <= dep[v] - dep[u])
            v = f[v][i];
    if (u == v)
        return u;
    for (int i = LOGN; i >= 0; i--)
    {
        if (f[u][i] != f[v][i])
            u = f[u][i], v = f[v][i];
    }
    return f[u][0];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(s, 0);
    for (int i = 1; i <= LOGN; i++)
        for (int j = 1; j <= n; j++)
            f[j][i] = f[f[j][i - 1]][i - 1];

    while (m--)
    {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
    return 0;
}

欧拉序+st表

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500'000;
int n, m, s;
vector<int> e[MAXN + 5];
// dis[i] 存 i 的深度
int dis[MAXN + 5];
// <深度, 点的编号>
vector<pair<int, int>> a;
// pos[i] 存 i 在 a 中第一次出现的下标
int pos[MAXN + 5];
void dfs(int u, int fa)
{
    a.push_back({dis[u], u});
    pos[u] = (int)a.size() - 1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dis[v] = dis[u] + 1;
        dfs(v, u);
        a.push_back({dis[u], u});
    }
}
// 处理 a 数组的 st 表
// st[i][j] 存 a[i] 开始的 2^j 个元素中的最小值下标
int st[MAXN * 2 + 5][20];
void initST()
{
    int len = a.size();
    for (int i = 0; i < len; i++)
        st[i][0] = i;
    for (int j = 1; (1LL << j) <= len; j++)
    {
        for (int i = 0; i + (1LL << j) - 1 < len; i++)
        {
            // i 为起点，2^j 长度的最小值下标
            int L = st[i][j - 1];
            int R = st[i + (1LL << (j - 1))][j - 1];
            if (a[L].first < a[R].first)
                st[i][j] = L;
            else
                st[i][j] = R;
        }
    }
}
int lca(int u, int v)
{
    if (pos[u] > pos[v])
        swap(u, v);
    // 找到 pos[u]~pos[v] 之间 first 最小的下标
    int len = pos[v] - pos[u] + 1;
    int j = log2(len);
    // pos[u] 开头的 2^j 和 pos[v] 结尾的 2^j 的最小值的最小值
    int L = st[pos[u]][j];
    int R = st[pos[v] - (1LL << j) + 1][j];
    if (a[L].first < a[R].first)
        return a[L].second;
    else
        return a[R].second;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dis[s] = 0;
    dfs(s, 0);
    initST();
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
    return 0;
}

Tarjan

dfs+并查集

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
const int MAXM = 500000;
int n, m, s;
vector<int> e[MAXN + 5];
//(v, 问题 id)
vector<pair<int, int>> ask[MAXN + 5];
int ans[MAXM + 5]; // 问题 id 为 i 的问题答案
// 每个点是否搜过了
bool vis[MAXN + 5];
// 并查集
int fa[MAXN + 5];
int findRoot(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = findRoot(fa[x]);
}
void dfs(int u, int from)
{
    for (int i = 0; i < ask[u].size(); i++)
        if (vis[ask[u][i].first])
            ans[ask[u][i].second] = findRoot(ask[u][i].first);
    vis[u] = true;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == from)
            continue;
        dfs(v, u);
        fa[v] = u;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    // 读询问
    for (int i = 1; i <= m; i++)
        ans[i] = 0;
    for (int i = 1; i <= m; i++)
    {
        int u, v, id;
        cin >> u >> v;
        id = i;
        if (u == v)
            ans[i] = u;
        else
        {
            ask[u].push_back({v, id});
            ask[v].push_back({u, id});
        }
    }
    // tarjan
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        vis[i] = false;
    }
    dfs(s, 0);
    for (int i = 1; i <= m; i++)
        cout << ans[i] << "\n";
    return 0;
}

重链剖分

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int n, m, s;
vector<int> e[MAXN + 5];
int fa[MAXN + 5], dep[MAXN + 5], siz[MAXN + 5], hson[MAXN + 5];
void dfs(int u, int father)
{
    fa[u] = father;
    siz[u] = 1;
    hson[u] = 0;
    dep[u] = dep[father] + 1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == father)
            continue;
        dfs(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[hson[u]])
            hson[u] = v;
    }
}
// 每个点的 dfs 序、按dfs序第 i 名的点编号是 rnk[i]，所属链顶端是 top
int tot, dfn[MAXN + 5], rnk[MAXN + 5], top[MAXN + 5];
void dfs_div(int u, int father)
{
    dfn[u] = ++tot;
    rnk[tot] = u;
    if (hson[u] != 0)
    {
        top[hson[u]] = top[u];
        dfs_div(hson[u], u);
    }
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == father || v == hson[u])
            continue;
        top[v] = v;
        dfs_div(v, u);
    }
}

int lca(int u, int v)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] < dep[top[v]])
            v = fa[top[v]];
        else
            u = fa[top[u]];
    }
    if (dep[u] > dep[v])
        return v;
    else
        return u;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(s, 0);
    tot = 0;
    top[s] = s;
    dfs_div(s, 0);
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
    return 0;
}

分类: 模板 · 更新时间 2026-11-8 14:43:14

朴素

倍增

欧拉序+st表

Tarjan

重链剖分

还没有账户？

登录