最近公共祖先(lca)

P3379 【模板】最近公共祖先（LCA）

1. 倍增

#include<bits/stdc++.h>
using namespace std;
const int MAXn = 500000;
const int MAXlogdep = 19;
const int MAXm = MAXn - 1;

int anc[MAXn + 10][MAXlogdep + 10], dep[MAXn + 10], n, q, s;
int head[MAXn + 10], next[MAXm * 2 + 10], toid[MAXm * 2 + 10], nown;
int lg2[MAXn + 10];

void Insert(int from, int to) {
    next[++nown] = head[from];
    head[from] = nown;
    toid[nown] = to;
}

inline int read() {
    register char c;
    while (c = getchar(), c < '0' || c >'9');
    register int x(c - '0');
    while (c = getchar(), c >= '0' && c <= '9') {
        x = (x << 1) + (x << 3) + c - '0';
    }
    return x;
}

void Dfs(int nodeid, int fa) {
    anc[nodeid][0] = fa;
    for (int i = 1; i <= MAXlogdep; ++i) {
        anc[nodeid][i] = anc[anc[nodeid][i - 1]][i - 1];
    }
    dep[nodeid] = dep[fa] + 1;
    for (int i = head[nodeid]; i; i = next[i]) {
        if (toid[i] != fa) {
            Dfs(toid[i], nodeid);
        }
    }
}

void Init() {
    for (int i = 1; i <= n; ++i) {
        lg2[i] = lg2[i - 1] + (1 << lg2[i - 1] == i);			
    }
    for (int i = 0; i <= n; ++i) {
        lg2[i]--;
    }
}

int Lca(int x, int y) {
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    while (dep[x] < dep[y]) {
        y = anc[y][lg2[dep[y] - dep[x]]];
    }
    if (x == y) {
        return y;
    }
    for (int i = lg2[dep[y]]; i >= 0; --i) {
        if (anc[x][i] != anc[y][i]) {
            x = anc[x][i];
            y = anc[y][i];
        }
    }
    return anc[x][0];
}

int main() {
    n = read();
    q = read();
    s = read();
    Init();
    int x, y;
    for (int i = 1; i < n; ++i) {
        x = read();
        y = read();
        Insert(x, y);
        Insert(y, x);
    }
    Dfs(s, 0);
    for (int i = 0; i < q; ++i) {
        x = read();
        y = read();
        printf("%d\n", Lca(x, y));
    }
    return 0;
}

2. 树剖

int Lca(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] > dep[top[y]]) {
            x = fa[top[x]];
        } else {
            y = fa[top[y]];
        }
  	}
    return dep[x] > dep[y] ? y : x;
}

3. 离线Tarjan

#include<cstdio>
#define re register
const int MAXn = 5e5;
const int MAXm = MAXn;
const int MAXq = 5e5;

int head[MAXn + 10], cntnex, nex[MAXm * 2 + 10], to[MAXm * 2 + 10];
void Insert(int u, int v) {
    nex[++cntnex] = head[u];
    head[u] = cntnex;
    to[cntnex] = v;
}

int headq[MAXn + 10], cntnexq, nexq[MAXq + 10], q[MAXq + 10];
void Insertq(int u, int v) {
    nexq[++cntnexq] = headq[u];
    headq[u] = cntnexq;
    q[cntnexq] = v;
}

int fa[MAXn + 10]; bool vis[MAXn + 10];
void Dfs1(int cur) {
    vis[cur] = 1;
    for (re int i = head[cur]; i; i = nex[i]) {
        if (vis[to[i]]) continue;
        fa[to[i]] = cur;
        Dfs1(to[i]);
    }
}
int times[MAXn + 10], ans[MAXq + 10];
void Dfs2(int cur) {
    ++times[cur];
    for (re int i = headq[cur]; i; i = nexq[i]) {
        int id = q[i];
        while (times[id] != 1) {
            id = fa[id];
        }
        ans[i] = id;
    }
    for (re int i = head[cur]; i; i = nex[i]) {
        if (times[to[i]]) continue;
        Dfs2(to[i]);
    }
    ++times[cur];
}

int n, Q, root, qid_nexq[MAXq + 10];
int main() {
    scanf("%d %d %d", &n, &Q, &root);
    for (re int i = 1, u, v; i < n; ++i) {
        scanf("%d %d", &u, &v);
        Insert(u, v);
        Insert(v, u);
    }
    Dfs1(root);
    for (re int i = 1, u, v; i <= Q; ++i) {
        scanf("%d %d", &u, &v);
        Insertq(u, v);
        qid_nexq[i] = cntnexq;
    }
    Dfs2(root);
    for (re int i = 1; i <= Q; ++i) {
        printf("%d\n", ans[qid_nexq[i]]);
    }
}