Almost-LCA in Tree

Revision en2, by skxqks, 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?

History

Revisions

Rev. Lang. By When Δ Comment
en2 skxqks 2019-11-20 02:02:42 92
en1 skxqks 2019-11-20 02:01:22 433 Initial revision (published)