SPOJ: LCA

#include <bits/stdc++.h>
using namespace std;

const int N = 1000;
const int logN = log2(N);

vector<int> adj[N + 1];
int rnk[N + 1], par[N + 1][logN + 1];

void DFS(int u, int p, int depth){
    par[u][0] = p;
    rnk[u] = depth;
    for(int v : adj[u]){
        if(v == p){
            continue;
        }
        DFS(v, u, depth + 1);
    }
}

int main(){

    int T;
    scanf("%d", &T);
    for(int t = 1; t <= T; ++t){
        cout << "Case " << t << ":\n";
        int nVertex;
        scanf("%d", &nVertex);
        for(int u = 1; u <= nVertex; ++u){
            adj[u].clear();
        }
        for(int u = 1; u <= nVertex; ++u){
            int nEdge;
            scanf("%d", &nEdge);
            for(int i = 1; i <= nEdge; ++i){
                int v;
                scanf("%d", &v);
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
        }
        DFS(1, 0, 1);
        for(int e = 1; e <= logN; ++e){
            for(int u = 1; u <= nVertex; ++u){
                par[u][e] = par[par[u][e - 1]][e - 1];
            }
        }
        int Q;
        scanf("%d", &Q);
        while(Q--){
            int u, v;
            scanf("%d%d", &u, &v);
            if(rnk[u] < rnk[v]){
                swap(u, v);
            }
            for(int e = logN; e >= 0; --e){
                if(rnk[par[u][e]] >= rnk[v]){
                    u = par[u][e];
                }
            }
            if(u == v){
                cout << u << '\n';
                continue;
            }
            for(int e = logN; e >= 0; --e)  {
                if(par[u][e] != par[v][e]){
                    u = par[u][e];
                    v = par[v][e];
                }
            }
            cout << par[u][0] << '\n';
        }
    }
    return  0;
}