C++ – LCA 最近公共祖先

络谷 P3379 [模板] 最近公共祖先 LCA

欧拉序+线段树

int cnt;
int dep[maxn];
int eoo[maxn];
int ooe[maxn << 1];

void dfs_ooe(int u, int f) {
    dep[u] = dep[f] + 1;
    ooe[++cnt] = u;
    eoo[u] = cnt;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].v;
        if (f == v) continue;
        dfs_ooe(v, u);
        ooe[++cnt] = u;
    }
}

int tree[maxn << 3];

void build(int rt, int l, int r) {
    if (l == r) {
        tree[rt] = ooe[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    tree[rt] = dep[tree[rt << 1]] < dep[tree[rt << 1 | 1]] ? tree[rt << 1] : tree[rt << 1 | 1];
}

int ask(int rt, int l, int r, int tl, int tr) {
    if (l == tl && r == tr) return tree[rt];
    int mid = (l + r) >> 1;
    if (tr <= mid) return ask(rt << 1, l, mid, tl, tr);
    if (tl > mid) return ask(rt << 1 | 1, mid + 1, r, tl, tr);
    int hl = ask(rt << 1, l, mid, tl, mid);
    int hr = ask(rt << 1 | 1, mid + 1, r, mid + 1, tr);
    return dep[hl] < dep[hr] ? hl : hr;
}

预处理

dfs_ooe(root, root);
build(1, 1, cnt);

查询

ask(1, 1, cnt, min(eoo[u], eoo[v]), max(eoo[u], eoo[v]))

倍增思想

lli fa[32][maxn];
lli dep[maxn];

void dfs_lca(lli u) {
    dep[u] = dep[fa[0][u]] + 1;
    for (lli i = 1; (1 << i) <= dep[u]; ++i)
        fa[i][u] = fa[i - 1][fa[i - 1][u]];
    for (lli i = head[u]; ~i; i = edge[i].nxt) {
        lli v = edge[i].v;
        if (v == fa[0][u]) continue;
        fa[0][v] = u;
        dfs_lca(v);
    }
}

lli find_lca(lli x, lli y) {
    if (x == y) return x;
    if (dep[x] > dep[y]) swap(x, y);
    for (lli i = 24; i >= 0; --i)
        if (dep[x] <= dep[y] - (1 << i))
            y = fa[i][y];
    if (x == y) return x;
    for (lli i = 24; i >= 0; --i)
        if (fa[i][x] != fa[i][y])
            x = fa[i][x], y = fa[i][y];
    return fa[0][x];
}