How to find Lowest Common Ancestor (LCA) if I can compute Kth ancestor of any node in O(logK) time ?

Правка en1, от hulk_baba, 2017-06-21 09:02:25

Hello, all. I was studying properties of the ancestors in the tree and solved a problem of finding the kth ancestor of any node in O(logK) time by pre-computing 2^jth parent of every node in O(NlogN) time. I am curious to know how can I apply this knowledge to find LCA of 2 given nodes efficiently?

Теги lca, #trees

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский hulk_baba 2017-06-21 09:02:25 399 Initial revision (published)