Before revision:  Using this framework , we develop the first work-efficient parallel batch-dynamic algorithm for dynamic trees that supports both subtree queries and path queries, as well as a variety of nonlocal queries such as centers and medians. We further investigate the applicability of the framework by analyzing map-reduce-based computations, and a random-mate list contraction algorithm , which, when dynamized, yields a simple solution to the batch-dynamic lists problem that matches the work bounds of the best known hand-crafted data structure .
After revision:  Our dynamic trees algorithm is obtained by applying our dynamization framework to the parallel tree contraction algorithm of Miller and Reif, and then performing a novel analysis of the computation distance of this algorithm under batch updates. We show that k updates can be performed in O(k \log(1+n/k)) work in expectation, which matches an existing algorithm of Tseng et al. while providing support for a substantially larger number of queries and applications .