Printing all paths of a tree and sorting the weight of edges Let $T=(V,E)$ be tree and each edge has a positive scalar weight. I need to print all paths in the tree and then sort the weight of edges in each paths. it needs $O(n^3\log(n))$ time.   To solve this problem we can rooted the tree in a leaf and print all vertices by preorder algorithm and in each step we insert the new edge weight. After meeting all vertices we can delete the root and consider another leaf as the root. The complexity seems $O(n^2\log(n)).$ Can we reduce the complexity, for example, $O(n^2)$?
You can't do better than $\Omega(n^3)$ running time.

In a tree, there is a path between every pair of vertices, so there are $\Theta(n^2)$ paths.  The average path length can be $\Theta(n)$.  So the total length of the output can be $\Theta(n^3)$.  Obviously, no algorithm can run faster than that, since it takes at least $\Theta(n^3)$ time just to write out the output.