lca_binary_lifting.cc

#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

vector<vector<long>> adj, T;
vector<long> par;
vector<long> st, en;

long timer = 0;
long max_height;

void preprocess(long u) {
   T[u][0] = par[u];
    for (int i = 1; i <= max_height; ++i)
      T[u][i] = T[T[u][i-1]][i-1];
   
   st[u] = ++timer;
   for (auto v : adj[u]) {
      preprocess(v);
   }
   en[u] = ++timer;
}

bool is_ancestor(long u, long v) {
   return st[u] <= st[v] && en[v] <= en[u];
}

long find_lca(long u, long v) {
   if (is_ancestor(u, v)) return u;
   if (is_ancestor(v, u)) return v;
   for (long i = max_height; i >= 0; --i) {
      if (!is_ancestor(T[u][i], v))
         u = T[u][i];
   }
   return T[u][0];
}

void clear() {
   adj.clear();
   par.clear();
   st.clear();
   en.clear();
   T.clear();
}

void reset(long N) {
   par.resize(N+1);
   adj.resize(N+1);
   st.resize(N+1);
   en.resize(N+1);
   timer = 0;
   max_height = ceil(log2(N));
   T.resize(N + 1, vector<long>(max_height + 1));
}


int main() {
   long T;
   scanf("%ld", &T);
   for (long case_id = 1; case_id <= T; ++case_id) {
   clear();
   long N;
   scanf("%ld", &N);
   reset(N);
   
   for (long i = 1; i <= N; ++i) {
      long m;
      scanf("%ld", &m);
      for (long j = 0; j < m; ++j) {
         long k;
         scanf("%ld", &k);
         adj[i].push_back(k);
         par[k] = i;
      }
   }
   // Find root.
   long root;
   for (long i = 1; i <= N; ++i) {
      if (par[i] == 0) {
         root = i;
         break;
      }
   }
   par[root] = root;
   // Pre-process.
   preprocess(root);
   
   // Answer queries.
   long Q;
   scanf("%ld", &Q);
   printf("Case %ld:\n", case_id);
   while (Q--) {
      long a, b;
      scanf("%ld%ld", &a, &b);
      printf("%ld\n", find_lca(a, b));
   }
   }
   return 0;
}