lca_euler_tour.cc

#include <cstdio>
#include <vector>

using namespace std;

vector<vector<long>> adj;
vector<long> d;
vector<long> par;
vector<long> euler;
vector<long> st, en;


void compute_euler_array(long u, long par_depth) {
   d[u] = par_depth + 1;
   st[u] = euler.size();
   if (adj[u].empty())
      euler.push_back(u);
   for (auto v : adj[u]) {
      euler.push_back(u);
      compute_euler_array(v, d[u]);
   }
   en[u] = euler.size();
   euler.push_back(u);
}

vector<long> seg_tree;

void clear() {
   adj.clear();
   d.clear();
   par.clear();
   euler.clear();
   st.clear();
   en.clear();
   seg_tree.clear();
}

void reset(long N) {
   par.resize(N+1);
   adj.resize(N+1);
   d.resize(N+1);
   seg_tree.resize(8 * N);
   st.resize(N+1);
   en.resize(N+1);
}



void init(long n, long b, long e) {
   if (b == e) {
      seg_tree[n] = euler[b];
      return;
   }
   init(2 * n, b, (b+e)/2);
   init(2 * n + 1, (b+e)/2 + 1, e);
   if (d[seg_tree[2 * n]] < d[seg_tree[2 * n +1]]) {
      seg_tree[n] = seg_tree[2 * n];
   } else {
      seg_tree[n] = seg_tree[2 * n + 1];
   }
}

long query(long n, long b, long e, long i, long j) {
   if (i > e || j < b) return -1;
   if (i <= b && e <= j) return seg_tree[n];
   long a1 = query(2 * n, b, (b+e)/2, i, j);
   long a2 = query(2 * n + 1, (b+e)/2 + 1, e, i, j);
   if (a1 == -1) return a2;
   if (a2 == -1) return a1;
   return d[a1] < d[a2] ? a1 : a2;
}

long find_lca(long a, long b) {
   return query(1, 0, euler.size() - 1, min(st[a], st[b]), max(en[a], en[b]));
}

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;
      }
   }
   // Pre-process.
   compute_euler_array(root, 0);
   init(1, 0, euler.size() - 1);
   
   // 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;
}