LCA.sublime-snippet

<snippet>
	<content><![CDATA[
const int MAXN = 5e4 + 10;
const int MAXLG = 17;

long long par[MAXN][MAXLG];
long long dist[MAXN];

vector <vector <long long>> V(MAXN , vector <long long>());

void dfs(long long v , long long pa = -1){
  par[v][0] = pa;
  if(pa + 1){
    dist[v] = dist[pa] + 1;
  }
  for(int i = 1 ; i < MAXLG ; ++i){
    par[v][i] = par[par[v][i - 1]][i - 1];
  }
  for(auto x : V[v]){
    if(pa != x){
      dfs(x , v);
    }
  }
}

long long LCA(long long u , long long v){
  if(dist[u] < dist[v]){
    swap(u , v);
  }
  for(int i = MAXLG - 1 ; i >= 0 ; --i){
    if(par[u][i] + 1 > 0 && dist[par[u][i]] >= dist[v]){
      u = par[u][i];
    }
  }
  if(u == v){
    return u;
  }
  for(int i = MAXLG - 1 ; i >= 0 ; --i){
    if(par[u][i] - par[v][i]){
      v = par[v][i] , u = par[u][i];
    }
  }
  return par[u][0];
}

long long getdis(long long u , long long v){
  return dist[u] + dist[v] - 2*dist[LCA(u , v)];
}

]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>least common ancestor</tabTrigger>
	<!-- Optional: Set a source to limit where the snippet will trigger -->
	<source>source.cpp , source.c++ , source.c , source.cxx , source.cc </source>
</snippet>