Tarjan's Offline Algorithm¶
Problems involving multiple queries have two types of solutions: online (online) and offline (offline). In the online approach, you must answer each query immediately, and until you respond to the current query, you cannot receive the next one. However, in the offline approach, you can receive all queries first and then start answering them.
In this section, we present an offline solution for the aforementioned problems. Since being online imposes a constraint, offline approaches have lower complexity.
This problem is straightforward. It suffices to collect all queries and then perform a DFS traversal from the root of the tree. When entering a vertex, we push it into a vector, and when exiting, we pop it. This way, while processing a vertex, the vertex itself and all its ancestors will be present in the vector, ordered by their height. Thus, when reaching a vertex, we can answer all its associated queries in \(O(1)\) time. This provides us with a linear approach.
The Solution to the LCA Problem¶
First, we receive all queries and create a list of related queries for each vertex. This can be done in linear time relative to the input size.
Then, we perform a DFS on the tree. When we enter a vertex, we create a set and place this vertex inside it. When we exit the vertex, we merge the set containing this vertex with its parent's set. With this approach, if we are on a vertex like u , any other vertex like v will reside in a set whose head is the lowest common ancestor of the two. The merge operations can be implemented using DSU , making the algorithm's complexity: \(O((n+q)*a(n))\) where \(a(n)\) is the inverse Ackermann function.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at آوریل 19, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
