Merge Leaf labeled trees
You can solve this using dynamic programming. Given trees $T_1,\ldots,T_n$, for each $1 \leq a \leq b \leq n$ compute the best way of concatenating $T_a,\ldots,T_b$. Details left to you.