LCA.cpp

/*** Lowest Common Ancestor ***/

#include <bits/stdc++.h>

using namespace std;

#define MAX 1005
#define MAXLOG 16
vector<int> adj[MAX];
bool vis[MAX];
int level[MAX], P[MAX][MAXLOG], n, parent[MAX];

void take_input()
{
    for(int i=0; i<MAX; i++) adj[i].clear();
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        int num;
        scanf("%d", &num);
        for(int j=1; j<=num; j++){
            int x;
            scanf("%d", &x);
            adj[i].push_back(x);
            adj[x].push_back(i);
        }
    }
}

void bfs(int root)
{
    memset(vis, false, sizeof vis);
    level[root] = 0;
    vis[root] = true;
    parent[root] = -1;
    queue<int> Q;
    Q.push(root);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        for(int i=0; i<adj[u].size(); i++){
            int v = adj[u][i];
            if(vis[v] == false){
                vis[v] = true;
                level[v] = level[u] + 1;
                parent[v] = u;
                Q.push(v);
            }
        }
    }
}

void preprocess()
{
    for(int i=1; i<=n; i++){
        for(int j=0; j<MAXLOG; j++) P[i][j] = -1;
    }
    for(int i=1; i<=n; i++) P[i][0] = parent[i];
    for(int j=1; j<MAXLOG; j++){
        for(int i=1; i<=n; i++){
            if(P[i][j-1] != -1){
                P[i][j] = P[P[i][j-1]][j-1];
            }
        }
    }
}

int findLCA(int u, int v)
{
    if(level[u] < level[v]) swap(u, v);
    int dist = level[u] - level[v];
    while(dist > 0){
        int raise_by = log2(dist);
        u = P[u][raise_by];
        dist -= (1<<raise_by);
    }
    if(u == v) return u;
    for(int j=MAXLOG-1; j>=0; j--){
        if(P[u][j] != -1 && (P[u][j] != P[v][j])){
            u = P[u][j];
            v = P[v][j];
        }
    }
    return parent[u];
}

int main()
{
    //freopen("in.txt", "r", stdin);
    int cases;
    scanf("%d", &cases);
    int caseno = 0;
    while(cases--){
        take_input();
        bfs(1);
        preprocess();
        printf("Case %d:\n", ++caseno);
        int q;
        scanf("%d", &q);
        for(int i=0; i<q; i++){
            int u, v;
            scanf("%d %d", &u, &v);
            printf("%d\n", findLCA(u, v));
        }
    }
}