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!

# | User | Rating |
---|---|---|

1 | tourist | 3748 |

2 | Benq | 3540 |

3 | Petr | 3470 |

4 | Radewoosh | 3355 |

5 | ecnerwala | 3347 |

6 | maroonrk | 3345 |

7 | jiangly | 3324 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 200 |

2 | Errichto | 197 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

5 | awoo | 185 |

6 | Um_nik | 182 |

7 | vovuh | 179 |

8 | Ashishgup | 175 |

9 | antontrygubO_o | 174 |

10 | -is-this-fft- | 173 |

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!

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/25/2021 20:20:39 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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).

please share links to read? Thanks.

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:

your code will fail queries with the same vertex, won't it?

code:is kind of pseudocodealso code:is python xdhere 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!!

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...