lcaa.sublime-snippet

<snippet>
	<content><![CDATA[

const int MAXN = 1e5 + 10;
const int LG = 17;
vector<vector<int>> g(MAXN);
int tim=0;
int parent[LG][MAXN];
int tin[MAXN], tout[MAXN], level[MAXN];
void dfs(int k, int par = -1 , int lvl = 0) {
  tin[k] = ++tim;
  parent[0][k] = par;
  level[k] = lvl;
  for(auto it : g[k]) {
    if(it == par)
      continue;
    dfs(it, k, lvl+1);
  }
  tout[k]=tim;
}

void precompute() {
  for(int i = 1 ; i < LG ; i++)
    for(int j = 0 ; j <= N; j++)
      if(parent[i-1][j] != -1)
        parent[i][j] = parent[i-1][parent[i-1][j]];
}

int LCA(int u, int v) {
  if(level[u] < level[v])
    swap(u,v);
  int diff = level[u] - level[v];
  for(int i = LG - 1 ; i >= 0 ; i--) {
    if((1<<i) & diff) {
      u = parent[i][u];
    }
  }
  if(u == v)
    return u;
  for(int i = LG - 1 ; i >=0 ; i--) {
    if(parent[i][u] != -1 && parent[i][u] != parent[i][v]) {
      u = parent[i][u];
      v = parent[i][v];
    }
  }
  return parent[0][u];
}
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>lcaa</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<!-- <scope>source.python</scope> -->
</snippet>