LCA

//LCAは最深根を基準とした時、
//2つのノードから最も近い共通のノードを探す。
//init にO(n*logn)だけ時間を使い、
//1回の検索はO(logn)でできる。
//root = x として最深根を指定する。
//ae(from,to) で枝を登録する。
//枝を登録後 init(node) で初期化。node はノード数。
//lca(a,b) でノードaとノードbの最短共通根のノード番号を得る。

#define MAX_V 55
#define MAX_LOG_V 8

vector<int> G[MAX_V];
int root;

int parent[MAX_LOG_V][MAX_V];
int depth[MAX_V];

void ae(int from, int to){
  G[from].push_back(to);
  G[to].push_back(from);
}

void dfsl(int v, int p, int d){
  parent[0][v] = p;
  depth[v] = d;
  for(int i = 0; i < G[v].size(); i++){
    if(G[v][i] != p)dfsl(G[v][i],v,d+1);
  }
}

// after ae!
void init(int V){
  dfsl(root,-1,0);
  for(int k = 0; k+1 < MAX_LOG_V; k++){
    for(int v = 0; v < V; v++){
      if(parent[k][v] < 0)parent[k+1][v]=-1;
      else parent[k+1][v] = parent[k][parent[k][v]];
    }
  }
}

int lca(int u, int v){
  if(depth[u] > depth[v])swap(u,v);
  for(int k = 0; k < MAX_LOG_V; k++){
    if((depth[v] - depth[u]) >> k & 1){
      v = parent[k][v];
    }
  }
  if(u == v)return u;
  for(int k = MAX_LOG_V - 1; k >= 0; k--){
    if(parent[k][u] != parent[k][v]){
      u = parent[k][u];
      v = parent[k][v];
    }
  }
  return parent[0][u];
}

int from[5] = {0,0,1,1,2};
int to[5] = {1,2,3,4,5};

int main(){
  root = 0;
  for(int i = 0; i < 5; i++){
    ae(from[i],to[i]);
  }
  init(6);
  cout << lca(3,5) << endl;
  return 0;
}