The level-ancestor problem is considered. Suppose a rooted tree T is g
iven for preprocessing. Answer quickly queries of the following form.
Given a vertex v and an integer i > 0, find the i th vertex on the pat
h from v to the root. Given any m, 1 less-than-or-equal-to m less-than
-or-equal-to log n, we achieve the following results: (1) O(log(m) n)
1 time using an optimal number of processors for preprocessing and con
stant time using a single processor for processing a query if m is con
stant. (2) O(log n) time using an optimal number of processors for pr
eprocessing and O(log n) time using a single processor for processing
a query. These results assume that the Euler tour of the tree and the
level (distance from the root) of each vertex are given. Without thes
e assumptions, the only change in result (1) above is that preprocessi
ng time increases to O(log n) An immediate corollary is a serial linea
r-time bound for preprocessing and a constant-time bound for processin
g a query. (C) 1994 Academic Press, Inc.