LowestCommonAncestor.sublime-snippet

<snippet>
	<content><![CDATA[
const int Nx = 2e5 + 10;
const int LOG = 25;
vector<int> gh[Nx];
int parent[Nx],level[Nx];
int lca[Nx][LOG],mxweight[Nx][LOG];
void dfs(int src,int par,int lvl){
	parent[src] = par;
	level[src] = lvl;
	lca[src][0] = par;
	for(auto x : gh[src]){
		if(x != par){
			dfs(x,src,lvl+1);
		}
	}
}
void buildLCA(){
	for(int i=1;i<LOG;i++){
		for(int j=1;j<Nx;j++){
			lca[j][i] = lca[lca[j][i-1]][i-1];
		}
	}
}
int findingLCA(int u,int v){
	if(level[u] < level[v]){
		swap(u,v);
	}
	int diff = level[u] - level[v];
	for(int i=0;i<LOG;i++){
		if(diff&(1<<i)){
			u = lca[u][i];
		}
	}
	if(u == v){
		return u;
	}
	for(int i=LOG-1;i>=0;i--){
		if(lca[u][i] && lca[u][i] != lca[v][i]){
			u = lca[u][i];
			v = lca[v][i];
		}
	}
	return lca[u][0];
}
int dist(int u,int v){
	return level[u] + level[v] - 2*level[findingLCA(u,v)];
}
void init(){
	dfs(1,-1,0);
	buildLCA();
}
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>lca</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<!-- <scope>source.python</scope> -->
</snippet>