ADDED   lib/dataStructure/lca.cpp
Index: lib/dataStructure/lca.cpp
==================================================================
--- lib/dataStructure/lca.cpp
+++ lib/dataStructure/lca.cpp
@@ -0,0 +1,39 @@
+//-------------------------------------------------------------
+// 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];
+	}
+};