Motivated by an application in computational geometry, we consider a novel
variant of the problem of efficiently maintaining a forest of dynamic rooted
trees. This variant includes an operation that merges two tree paths. In contrast
to the standard problem, in which a single operation can only add or delete one
arc, one merge can add and delete up to a linear number of arcs. In spite of
this, we develop three different methods that need only polylogarithmic time per
operation. The first method extends a solution of Farach and Thorup [1998] for
the special case of paths. Each merge takes O(log^{2} n) amortized time
on an n-node forest and each standard dynamic tree operation takes O(log n) time;
the latter bound is amortized, worst case, or randomized depending on the
underlying data structure. For the special case that occurs in the motivating
application, in which arbitrary arc deletions (cuts) do not occur, we give a
method that takes O(log n) time per operation, including merging. This is best
possible in a model of computation with an Omega(n log n) lower bound for sorting
n numbers, since such sorting can be done in O(n) tree operations. For the
even-more-special case in which there are no cuts and no parent queries, we give
a method that uses standard dynamic trees as a black box: each mergeable tree
operation becomes a constant number of standard dynamic tree operations. This
third method can also be used in the motivating application, but only by changing
the algorithm in the application. Each of our three methods needs different
analytical tools and reveals different properties of dynamic trees.