1 files changed, 32 insertions, 0 deletions
diff --git a/content/graph/LCA_sparse.cpp b/content/graph/LCA_sparse.cpp
new file mode 100644
index 0000000..3e87cde
--- /dev/null
+++ b/content/graph/LCA_sparse.cpp
@@ -0,0 +1,32 @@
+struct LCA {
+	vector<ll> depth;
+	vector<int> visited, first;
+	int idx;
+	SparseTable st; //sparse table @\sourceref{datastructures/sparseTable.cpp}@
+
+	void init(vector<vector<int>>& adj, int root) {
+		depth.assign(2 * sz(adj), 0);
+		visited.assign(2 * sz(adj), -1);
+		first.assign(sz(adj), 2 * sz(adj));
+		idx = 0;
+		dfs(adj, root);
+		st.init(depth);
+	}
+
+	void dfs(vector<vector<int>>& adj, int v, ll d=0) {
+		visited[idx] = v, depth[idx] = d;
+		first[v] = min(idx, first[v]), idx++;
+
+		for (int u : adj[v]) {
+			if (first[u] == 2 * sz(adj)) {
+				dfs(adj, u, d + 1);
+				visited[idx] = v, depth[idx] = d, idx++;
+	}}}
+
+	int getLCA(int u, int v) {
+		if (first[u] > first[v]) swap(u, v);
+		return visited[st.queryIdempotent(first[u], first[v] + 1)];
+	}
+
+	ll getDepth(int v) {return depth[first[v]];}
+};