Random linear arrangement of a tree with constrained edge lengths

Question

Let $T$ be a tree with $V$ and edges $E$. Let a linear arrangement $\pi$ of $T$ be a bijective mapping from nodes to integers in the range $\{1, \dots, |V|\}$. You can think of $\pi$ as defining the position of each node in an arrangement on a line.

Now define the length of an edge $E = \{u,v\}$ in $T$ under $\pi$ to be the absolute value of the difference in positions for $u$ and $v$ according to the linear arrangement $\pi$: \begin{equation} l_\pi(u,v) = |\pi(u) - \pi(v)|. \end{equation}

Linear arrangements of this kind are studied in, for example, the Optimal Linear Arrangement problem (Chung, 1984), where the goal is to find a $\pi$ for a fixed $T$ which minimizes $\sum_{\{u,v\} \in E} l_\pi(u,v)$.

My problem is: given a tree $T$ and a linear arrangement $\pi$, generate new linear arrangement $\pi^\prime$ randomly at uniform from the set of possible linear arrangements of $T$ while preserving the same distribution over edge lengths as in the original $\pi$.

An example tree with linear arrangement $\pi$ is shown below. Each edge is marked with its length. The distribution of edge lengths in this tree under this particular linear arrangement is $(1, 1, 1, 2, 2)$ (3 of length 1 and 2 of length 2).

Now here is the same tree under a different linear arrangement $\pi^\prime$, which has the same distribution of edge lengths $(1,1,1,2,2)$.

I am looking for an efficient algorithm to generate random linear arrangements that preserve the distribution over edge lengths. Here is a baseline rejection-sampling algorithm:

1. Starting with tree $T$ with $n$ nodes and linear arrangement $\pi$, calculate the list of edge lengths for $T$ under $\pi$. Call this $L$.
2. Generate a random linear arrangement $\pi^\prime$ by drawing from the set of $n!$ linear arrangements of $T$.
3. Calculate the list of edge lengths for $T$ under $\pi^\prime$. Call this $L^\prime$. If $L^\prime = L$, accept the sample. If $L^\prime \neq L$, reject the sample and go to step 2.

I’m looking for an algorithm to draw a random sample from the linear arrangements that match $L$ which is faster than rejection sampling. No need to enumerate the whole set (although that would be nice too).

This question is related to, but distinct from, my earlier question: Generate random labeled tree with constrained edge lengths. In that question, I was looking for random trees. In this question, I am looking for random linear arrangements of a fixed tree, while preserving the topology of the tree.