Lowest Common Ancestor Algorithm

namespace LCA{
  #define BD 20
  int lca(int u, int v) {
  	if(dep[u] < dep[v]) swap(u,v);
  	int diff = dep[u] - dep[v];
  	for(int i=0; i<BD; i++) if((diff>>i)&1 ) u = pa[u][i];
  	if(u == v) return u;
  	for(int i=BD-1; i>=0; i--) if(pa[u][i] != pa[v][i]) {
  		u = pa[u][i];
  		v = pa[v][i];
  	}
  	return pa[u][0];
  }
  void set_up_lca(int nn){
    for(int i = 1 ; i <= BD ; i++)
      for(int j = 0; j <= nn ; j++)
        if(pa[j][i-1] != -1) pa[j][i] = pa[pa[j][i-1]][i-1] ;
  }
  void dfs(int pos, int depth, int prev){
    pa[pos][0] = prev;
    dep[pos] = depth;
    for (int i=head[pos];i;i=edge[i].nxt){
      int v = edge[i].v;
      if (v==prev) continue;
      dfs(v,depth+1,pos);
    }
  }
  #undef BD
}