First it is shown that for any rooted tree T with n vertices, and para
meter m greater than or equal to n, there is a ''shortcutting'' set S
of at most m arcs from the transitive closure T of T such for any (v,
w) is an element of T, there is a dipath in T boolean OR S from v to
w of length O(alpha(m, n)). An equivalent result has been achieved by
Chazelle (Algorithmica 2 (1987), 337-361), but our proof is algorithm
ically simpler, and, in particular, it lends itself well to paralleliz
ation. More precisely, suppose that weights from a semigroup are assig
ned to the area of T. Then we can preprocess T in time O(log n) with O
(m/log n) processors on a CREW PRAM such that for any (u, w) is an ele
ment of T, we can find the weight of the path from u to w in O(cu(m,n
)) sequential time. Alon and Schieber (''Optimal Preprocessing for Ans
wering On-Line Product Queries,'' Technical Report 71/87, Tel Aviv Uni
versity, 1987) have claimed that such a parallelization is possible fo
r Chazelle's result. This claim is used in the optimal parallel sensit
ivity analysis for minimum spanning trees by Dixon (''Minimum Spanning
Tree Verification, Fast Priority Queues, and Massively Parallel Facto
ring,'' Ph.D. thesis, Princeton University,; 1993). However, Alon and
Schieber did not give the details of the parallelization. Here we pres
ent a full proof and our algorithms, both the sequential and the paral
lel versions, are rather simple, hence likely to be of practical relev
ance. (C) 1997 Academic Press.