LCA-倍増法（オンライン）

http://www.tuicool.com/articles/N7jQV32
 
1. DFSは、すべてのノードの深さと親ノードを前処理する。  

inline void dfs(int u) {  int i;  for(i=head[u];i!=-1;i=next[i])  {   if (!deep[to[i]])   {    deep[to[i]] = deep[u]+1;    p[to[i]][0] = u; //p[x][0]  x     u;    dfs(to[i]);   }  } }

2. 最初の各点の2^j祖先は誰ですか？   2^j  (j =0…ロゴマークは先祖の倍、先祖の倍は父、先祖の2倍は父の2倍は父……。    

void init() {  int i,j;  //p[i][j]  i    2^j    for(j=1;(1<<j)<=n;j++)   for(i=1;i<=n;i++)    if(p[i][j-1]!=-1)     p[i][j]=p[p[i][j-1]][j-1];//i  2^j    i  2^(j-1)    2^(j-1)   }

3.深さの大きいノードから深さの小さいノードの同層に上昇し、この場合、両ノードが同じであれば、直接にこのノード、すなわちlcaに戻る。  
さもなくば、倍増法を利用して最小の深さのを探し当てます。     p[a][j]p[b][j]この時彼らの父p[a][0]はlcaです。  

int lca(int a,int b)//       {  int i,j;  if(deep[a]<deep[b])swap(a,b);  for(i=0;(1<<i)<=deep[a];i++);  i--;  // a，b         for(j=i;j>=0;j--)   if(deep[a]-(1<<j)>=deep[b])    a=p[a][j];  if(a==b)return a;  //   ，       2^j，              for(j=i;j>=0;j--)  {   if(p[a][j]!=-1&&p[a][j]!=p[b][j])   {    a=p[a][j];    b=p[b][j];   }  }  return p[a][0]; }