lca.cpp

Bài viết đang được chỉnh sửa

Bài toán

Cho một cây, và các truy vấn p q, với mỗi truy vấn, tìm tổ tiên chung gần nhất.

Độ phức tạp

truy vấn O(logn)

#include <stdio.h>

#include <vector>

using namespace std;

vector<int> a[230997]; //

int parent[230997];    //

int l[230997];

int M[230997][23];

int n;

void direct(int u) {

    for (int v : a[u])

        if (v != parent[u]) {

            parent[v] = u;

            l[v] = l[u] + 1;

            direct(v);

        }

}

void make_lca() {

    for (int i = 1; i <= n; i++)

        M[i][0] = parent[i];

    for (int k = 1; k <= 20; k++)

        for (int i = 1; i <= n; i++)

            M[i][k] = M[M[i][k - 1]][k - 1];

}

int lca(int p, int q) {

    // ensure l[p]=l[q]

    for (int i = 20; i >= 0; i--)

        if (l[M[p][i]] >= l[q])

            p = M[p][i];

    for (int i = 20; i >= 0; i--)

        if (l[M[q][i]] >= l[p])

            q = M[q][i];

    if (p == q)

        return p;

    for (int i = 20; i >= 0; i--)

        if (M[p][i] != M[q][i]) {

            p = M[p][i], q = M[q][i];

        }

    return parent[p];

}

main() {

    int T;

    scanf("%d", &T);

    for (int t = 1; t <= T; t++) {

        scanf("%d", &n);

        for (int i = 1; i <= n; i++) {

            a[i].clear();

            parent[i] = 0;

        }

        printf("Case %d:\n", t);

        for (int i = 1; i <= n; i++) {

            int m;

            scanf("%d", &m);

            for (int j = 1; j <= m; j++) {

                int p;

                scanf("%d", &p);

                a[i].push_back(p);

            }

        }

        for (int i = 1; i <= n; i++)

            if (parent[i] == 0) {

                parent[i] = i;

                l[i] = 1;

                direct(i);

            }

        make_lca();

        int nQuery;

        scanf("%d", &nQuery);

        while (nQuery--) {

            int p, q;

            scanf("%d%d", &p, &q);

            printf("%d\n", lca(p, q));

        }

    }

}

Nhận xét