vkditya0997's blog

Fastest way to calculate LCA?
By vkditya0997, history, 8 years ago, In English

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!

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (15)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

There is an also Tarjan's off-line lowest common ancestors algorithm that uses DSU and works in O(N * DSU).

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

There is a great tutorial on TopCoder: https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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][0]].insert(i)
    q[queries[i][1]].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)
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    hard to make a bug

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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    code: is kind of pseudocode also code: is python xd

    → Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

here you can find something good.

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply