optimal lifted phylogenetic alignment - how to improve time complexity?
Consider a node $x$ with children $x_1,\ldots,x_d$, and denote by $N(v)$ the number of leaves in the subtree $T(v)$ rooted at $v$. We can implement the processing of $x$ as follows:


Go over $1 \leq i \leq d$:

Choose a leaf $f_i \in T(x_i)$ as the label of $x$ and $x_i$.


For all $j \neq i$, choose the leaf $f_j \in T(x_j)$ that minimizes $D(f_i,f_j) + d(x_j,f_j)$.


Store $d(x,f_i) = \sum_{j \neq i} [D(f_i,f_j) + d(x_j,f_j)]$.



The processing time of $x$ is proportional to
$$
\sum_{i=1}^d N(x_i) \times \sum_{j \neq i} N(x_j) = \left(\sum_{i=1}^d N(x_i)\right)^2 - \sum_{i=1}^d N(x_i)^2 = N(x)^2 - \sum_{i=1}^d N(x_i)^2.
$$
Summing over all nodes $x$ up to the root $r$, we see that the total processing time is proportional to $N(r)^2 = k^2$.