Artifact Content
Not logged in

Artifact df81a86e707e972b64432cf012947003249a8816


//-------------------------------------------------------------
// The Least Common Ancestor
//
// Verified by
//   - ICPC 2021 Yokohama Regional I
//-------------------------------------------------------------


template<int K=17>
struct Lca
{
	const int N;
	const vector<int>& depth;
	vector<vector<int>> jump;
	Lca(int N, const vector<int>& parent, const vector<int>& depth)
		: N(N), depth(depth), jump(K, vector<int>(N, -1))
	{
		jump[0] = parent;
		for(int k=0; k+1<K; ++k)
		for(int v=0; v<N; ++v)
			if(jump[k][v] != -1)
				jump[k+1][v] = jump[k][jump[k][v]];
	}

	int operator()(int a, int b) const {
		if(depth[a]>depth[b]) swap(a,b);
		for(int k=0; k<K; ++k)
			if((depth[b]-depth[a]) & (1<<k))
				b = jump[k][b];
		if(a == b)
			return a;
		for(int k=K-1; k>=0; --k)
			if(jump[k][a] != jump[k][b]) {
				a = jump[k][a];
				b = jump[k][b];
			}
		return jump[0][a];
	}
};