notebook/code/LCA.cpp

// use union find
// u : root
// G : graph (children lists)
// q : queries q[u] : set of v for asking (u, v) (must be symmetric)
// 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[], 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(int v : q[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 q[6];
  q[3].push_back(2); q[2].push_back(3);
  int f[6]; int a[6]; bool c[6] = {0, 0, 0, 0, 0, 0};
  Tarjan(0, G, q, f, a, c);
}