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();
}
}