Problems using LCA form arhive.
Moderator: Board moderators
Problems using LCA form arhive.
Does anyone knows problemes in the arhive that use or can use LCA (Lowest common ancestor)? Or from other sites ...
Thanks
Thanks
can anybody explain me O(log n) LCA algo or give any link?
Giorgi Saghinadze
http://acm.uva.es/problemset/usersjudge.php?user=32393
http://acm.uva.es/problemset/usersjudge.php?user=32393
In Gusfield ("Algorithms on Strings, Trees, and Sequences"), ch.8, they describe a constant time LCA with linear preprocessing.
I tried reading it, but that just went (waaay) over my head. They map the tree to a complete binary tree in linear time in some funky way, that part I don't understand. Then finding LCA is easy (that part I kinda understand).
It is actually a good book, but is a bit hard for me to follow.
I tried reading it, but that just went (waaay) over my head. They map the tree to a complete binary tree in linear time in some funky way, that part I don't understand. Then finding LCA is easy (that part I kinda understand).
It is actually a good book, but is a bit hard for me to follow.
http://www14.in.tum.de/konferenzen/Jass ... kiefer.pdf
very interesting link
this algorithm finds LCA using minimizator
very interesting link
this algorithm finds LCA using minimizator
Giorgi Saghinadze
http://acm.uva.es/problemset/usersjudge.php?user=32393
http://acm.uva.es/problemset/usersjudge.php?user=32393
There is also a very easy to code algorithm due to Tarjan, in which you find the lca of several pairs of vertices during a dfs of the tree (in O(V+Q+alfa(V+Q)), where V is the number of vertices, Q the number of queries and alfa is the very slowgrowing inverse of the Ackermann function). You can find it in an exercise somewhere in Cormen's book.

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
Actually, you can do the precalc in O(nlogn) time by converting into an +/1 RMQ problem in linear time, and then do the queries in O(1).
Of course, you can also precalc in O(n) and queries in O(1), and that part isn't so bad using the big/small universe paradigm. The general RMQ>LCA is probably the hardest part, but the other parts are very easy to understand.
The paper is here:
http://www.cs.sunysb.edu/~bender/pub/lca.ps
Of course, you can also precalc in O(n) and queries in O(1), and that part isn't so bad using the big/small universe paradigm. The general RMQ>LCA is probably the hardest part, but the other parts are very easy to understand.
The paper is here:
http://www.cs.sunysb.edu/~bender/pub/lca.ps
Check out http://www.algorithmist.com !