lca.cpp (2)

Code này AC rồi, bài viết đang được chỉnh sửa.

#include <stdio.h>

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

#define long long long

#define N 100005

int n, t, T, m, Root;

int Level[N], Parent[21][N];

vector<int> a[N];

void visit(int u) {

    for (int v : a[u]) {

        Parent[0][v] = u;

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

        visit(v);

    }

}

int lca(int x, int y) {

    for (int k = 10; k >= 0; k--)

        if (Level[Parent[k][x]] >= Level[y])

            x = Parent[k][x];

    for (int k = 10; k >= 0; k--)

        if (Level[Parent[k][y]] >= Level[x])

            y = Parent[k][y];

    for (int k = 10; k >= 0; k--)

        if (Parent[k][x] != Parent[k][y]) {

            x = Parent[k][x], y = Parent[k][y];

        }

    while (x != y) {

        x = Parent[0][x];

        y = Parent[0][y];

    }

    return x;

}

void enter() {

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

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

        int n0, x;

        scanf("%d", &n0);

        while (n0--) {

            scanf("%d", &x);

            a[i].push_back(x);

            Root ^= x;

        }

    }

}

int main() {

    scanf("%d", &T);

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

        Root = 0;

        scanf("%d", &n);

        enter();

        Parent[0][Root] = Root;

        visit(Root);

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

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

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

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

        scanf("%d", &m);

        while (m--) {

            int x, y;

            scanf("%d%d", &x, &y);

            printf("%d\n", lca(x, y));

        }

        for (int i = 1; i <= n; ++i) a[i].clear();

    }

}