CPP习题-LCA

C++进阶

LCA（最近公共祖先）（树上问题）

例题ACWING1172

const int N = 1e5 + 5;
int h[N], cnt, nxt[N], to[N], f[N][20], dep[N], rt, n, m;

邻接表部分

void add(int a, int b) {
    to[++cnt] = b, nxt[cnt] = h[a], h[a] = cnt;
}

一遍dfs预处理深度和从u向上走2^i深度到达的点是什么

void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for (int i = 1; i < 17; i++)
        f[u][i] = f[f[u][i - 1]][i - 1];
    for (int i = h[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == fa)
            continue;
        dfs(v, u);
    }
}

真正LCA

int lca(int a, int b) {
    if (dep[b] > dep[a])//统一将a变成更深的
        swap(a, b);
    for (int i = 16; i >= 0; i--)//先让a,b在统一高度,再同时向上走
        if (dep[f[a][i]] >= dep[b])
            a = f[a][i];
    if (a == b)
        return a;
    for (int i = 16; i >= 0; i--)
        if (f[a][i] != f[b][i])
            a = f[a][i], b = f[b][i];
    return f[a][0];
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    dfs(rt, 0);
    cin >> m;
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        int l = lca(a, b);
        if (l == a)
            cout << 1;
        else if (l == b)
            cout << 2;
        else
            cout << 0;
        cout << endl;
    }
    return 0;
}