  Most computational models of dependency syntax consist of distributions over
spanning trees. However, the majority of dependency treebanks require that
every valid dependency tree has a single edge coming out of the ROOT node, a
constraint that is not part of the definition of spanning trees. For this
reason all standard inference algorithms for spanning trees are suboptimal for
inference over dependency trees.
  Zmigrod et al. (2021b) proposed algorithms for sampling with and without
replacement from the dependency tree distribution that incorporate the
single-root constraint. In this paper we show that their fastest algorithm for
sampling with replacement, Wilson-RC, is in fact producing biased samples and
we provide two alternatives that are unbiased. Additionally, we propose two
algorithms (one incremental, one parallel) that reduce the asymptotic runtime
of algorithm for sampling k trees without replacement to O(kn3). These
algorithms are both asymptotically and practically more efficient.
