Блог пользователя vkditya0997

Автор vkditya0997, история, 8 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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) 
»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

here you can find something good.

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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