notebook/code/LCA.cpp

// use union find
// u : root
// G : graph (children lists)
// q : queries q.first[u] : set of v for asking (u, v), q.second miroir
// f : union-find array, a : ancestor, c : colour (init false)
void makeSet(int *C, int i) { C[i] = i; }
void Tarjan(int u, VI G[], pair<VI*, VI*> q, int f[], int a[], bool c[]) {
  makeSet(f,u);
  a[u]=u;
  for(int v : G[u]) { // for each children of us
    Tarjan(v, G, q, f, a, c);
    unite(f,u,v);
    a[find(f,u)] = u;
  }
  c[u] = true;
  for(VI* qu : {q.first, q.second})
    for(int v : qu[u])
      if(c[v])
        cout<<"LCA("<<u<<','<<v<<")="<<a[find(f,v)]<<endl;
}
void test() {
  VI G[6];
  G[0].push_back(1); G[0].push_back(2); G[2].push_back(3); G[2].push_back(4); G[3].push_back(5);
  VI q1[6], q2[6];
  q1[3].push_back(2); q2[2].push_back(3);
  int f[6]; int a[6]; bool c[6] = {0, 0, 0, 0, 0, 0};
  Tarjan(0, G, make_pair(q1, q2), f, a, c);
}