### vkditya0997's blog

By vkditya0997, history, 4 years ago, Hello Codeforces,

I was learning about LCA today. I found some video tutorial which explained a naive method.

So, I wanted to know the best Algorithm for finding LCA between two nodes.

Thank you! lca, Comments (16)
 » I know one method in which we do euler tour over the tree and create a depth sequence.Then we find the minimum depth vertex between first and last occurrence of the vertex using any data structure that give RMQ(segment tree,sparse table).
•  » » » I am busy until the transfer window is open..please search on internet you will find all information.
•  » » » Here it is: LCA to RMQ
 » You can turn LCA problem to RMQ±1 and then use Farach Colton Bender algorithm, which solves RMQ±1 in O(n) preprocessing and O(1) for query. Of course sparse table is easier to code and O(n log n) and O(n) don't differ too much for n ~10^5, but since you asked for fastest way...Btw, fastest way to code LCA is binary lifting
•  » » I found that LCA by binary lifting take O(NlogN) for preprocessing, and O(logN) for query! How can it be fastest? Or did I get it wrong... source — https://cp-algorithms.com/graph/lca_binary_lifting.html other — https://www.geeksforgeeks.org/lca-in-a-tree-using-binary-lifting-technique/
•  » » » "Fastest to code" means "easiest and fastest to write"
 » There is an also Tarjan's off-line lowest common ancestors algorithm that uses DSU and works in O(N * DSU).
 » There is a great tutorial on TopCoder: https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/
 » We have N nodes and Q queries. The best ways of counting LCA are: 1) Segment tree. Dfs the tree with timer, built segment tree and find minimum on segment. O(N + Q * log(N)) 2) Sparse table. Absolutely the same, just find minimum with it. O(N * log(N) + Q) 3) Farach Colton Bender. There is some magic that i don't understand, but it use the fact that two adjacent values in array differs only on 1. You can read about it on e-maxx. However, it's the fastest way to solve LCA. O(N + Q)
 » I like this offline algorithm: store set of unanswered queries in each vertex, then run dfs and merge sets. Not optimal, but easy to remember, easy to implement, hard to make a bug. Kind of pseudocode: for i in range(queries): q[queries[i]].insert(i) q[queries[i]].insert(i) def dfs(v, p): for to in g[v]: if to == p: continue dfs(to, v) if len(q[v]) < len(q[to]): swap(q[v], q[to]) for i in q[to]: if i in q[v]: q[v].delete(i) lca[i] = v else: q[v].insert(i) 
•  » » hard to make a bug your code will fail queries with the same vertex, won't it?
•  » » code: is kind of pseudocode also code: is python xd
 » here you can find something good.
 » Thank you guys!I read O(N*Sqrt(N)), and reduction of LCA to RMQ technique.learnt lot many things. and also I can see Tarjan Offline Algo related comments. Can someone provide Time Complexity and links to read it?Once again, Thank you Codeforces!!
•  » » 4 years ago, # ^ | ← Rev. 2 →   https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm I think this link will be sufficient for pseudo code(you can read more about it from the clrs book http://is.ptithcm.edu.vn/~tdhuy/Programming/Introduction.to.Algorithms.pdf), try implementing on your own...