Almost-LCA in Tree

Правка en2, от fmqjpt, 2019-11-20 02:02:42

Is there a simple solution to the below problem in $$$O(1)$$$ per query with reasonable, such as $$$O(NlogN)$$$, preprocessing?

Problem: Given two nodes $$$u$$$ and $$$v$$$ in a tree, find the second node on the path from $$$u$$$ to $$$v$$$.

If $$$u$$$ is not an ancestor of $$$v$$$ this is easy. If $$$u$$$ is an ancestor of $$$v$$$ though then the answer is one of the children of $$$u$$$. You could compute the answer with jump-pointers in $$$O(log N)$$$ per query, but is there any easy way to find it in $$$O(1)$$$ per query?

Теги trees, data structures

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский fmqjpt 2019-11-20 02:02:42 92
en1 Английский fmqjpt 2019-11-20 02:01:22 433 Initial revision (published)