  Dynamic trees are a well-studied and fundamental building block of dynamic
graph algorithms dating back to the seminal work of Sleator and Tarjan
[STOC'81, (1981), pp. 114-122]. The problem is to maintain a tree subject to
online edge insertions and deletions while answering queries about the tree,
such as the heaviest weight on a path, etc. In the parallel batch-dynamic
setting, the goal is to process batches of edge updates work efficiently in low
($\text{polylog}\ n$) span. Two work-efficient algorithms are known,
batch-parallel Euler Tour Trees by Tseng et al. [ALENEX'19, (2019), pp. 92-106]
and parallel Rake-Compress (RC) Trees by Acar et al. [ESA'20, (2020), pp.
2:1-2:23]. Both however are randomized and work efficient in expectation.
Several downstream results that use these data structures (and indeed to the
best of our knowledge, all known work-efficient parallel batch-dynamic graph
algorithms) are therefore also randomized.
  In this work, we give the first deterministic work-efficient solution to the
problem. Our algorithm maintains a dynamic parallel tree contraction subject to
batches of $k$ edge updates deterministically in worst-case $O(k \log(1 +
n/k))$ work and $O(\log n \log^{(c)} k)$ span for any constant $c$. This allows
us to implement parallel batch-dynamic RC-Trees with worst-case $O(k \log(1 +
n/k))$ work updates and queries deterministically. Our techniques that we use
to obtain the given span bound can also be applied to the state-of-the-art
randomized variant of the algorithm to improve its span from $O(\log n \log^*
n)$ to $O(\log n)$.
