Abstract
In this paper, we consider the LCA problem on a tree with an unfixed root. A tree T is with an unfixed root if its root is not fixed and any node in T may be chosen as the root of T. The problem is to preprocess T such that a query 'What is the LCA of v 1 and v 2 if a node w is chosen as the root of T?' can be answered quickly for any triplex of nodes v 1 , v 2 , and w. In this paper, we show that each query of the LCA problem on a tree with an unfixed root can be answered in O(1) time after an O(n) time preprocessing.