lca.md

Lowest Common Ancestor

struct Lca{ //  This is zero based
	vector<vector<int>> par;
	vector<int> time_in, time_out, dist;
	int timer;
	Lca(vector<int> g[], int n){
		par = vector<vector<int>>(n,vector<int>(20,-1));
		time_in = vector<int>(n);
		time_out = vector<int>(n);
		dist = vector<int>(n, 0);
		timer = 0;
		par[0][0] = 0;
		dfs(g,0,-1);
	}
	
	void dfs(vector<int> g[], int node, int parent){
		time_in[node] = timer++;
		for(int i = 1 ; i < 20 ; i++) par[node][i] = par[par[node][i-1]][i-1];
		for(int i : g[node]){
			if(i != parent){
				par[i][0] = node;
				dist[i] = dist[node] + 1;
				dfs(g, i, node);
			}
		}
		time_out[node] = timer++;
	}
	
	inline bool isAncestor(int x, int y){ // is x ancestor of y ? 
		return time_in[x] <= time_in[y] && time_out[x] >= time_out[y];
	}
	
	int getLca(int x, int y){
		if(isAncestor(x, y)) return x;
		if(isAncestor(y, x)) return y;
		for(int i = 19 ; i >= 0 ; i--){
			if(!isAncestor(par[x][i], y)) x = par[x][i];
		}
		return par[x][0];
	}
	
	int getDist(int x, int y){
		int lca = getLca(x, y);
		return dist[x] + dist[y] - (dist[lca]<<1);
	}
};