An O(m log n) algorithm for the max + sum spanning tree problem

In a graph in which each edge has two weights, the max + sum spanning tree problem seeks a spanning tree that has the minimum value for the combined total of the maximum of one of the edge weights and the sum of the other weights among all the spanning trees in the graph. Exploiting an efficient data structure, an O(m log n) algorithm is presented for solving this problem. This improves the currently known bound of O(mn).