First, some notations: The tree given in the input will be denoted as T. The graph we are to find will be denoted as G. If u and v are nodes in G (and also in T), the link between u and v in G (and possibly in T) will be denoted as uv. The path between u and v in T will be denoted as uTv (such path always exists and is unique, as T is a tree).
How does the graph G look like? Consider any two nodes a and b such that ab is not in T. Since G is complete the link ab is in G. What is its weight? Consider some link (say cd) in the aTb path. If weight of ab is not greater than weight of cd then we can obtain a new spanning tree T′ from T by the removing link cd and adding link ab. Clearly T′ is also a spanning tree of G and its weight is not greater than weight of T. But it contradicts the property of G that T is its only minimum spanning tree.
All this means that the following propertry is necessary for G:
Each link ab not in T has weight strictly greater than any link in the aTb path.
A natural question arises: Is this property also sufficient? The answer is yes. To see this consider a spanning tree U of G which is different from T. Since U is different from T it contains a link (say ab) which is not in T. When we remove link ab form U it breaks into two components (one of them contains a, the other contains b). Clearly the path aTb has to contain a link (say cd) which connects these two components (otherwise it would not be able to connect a and b). By joining these components with link cd we obtain new spanning tree U′ of G. But weight of U′ is less than weight of U because weight of the link ab is greater than weight of the link cd. This means that U was not a minimum spanning tree of G.
Now the solution is clear. For each pair of nodes a and b such that ab is not in T we find the path aTb and determine minimum possible weight for link ab which satisfies the above property. This can be done in time proportional to N2 (where N is number of nodes in T).
There was an even faster solution that mimics Kruskal’s algorithm to construct the minimum spanning tree. We simply process all the given edges ordered by their weight. Each time we add a new edge with weight w, we connect two components into one. At this moment, we can also connect all other pairs of vertices in those two components, using edges with weight w + 1. The constructed graph is obviously the same as in the previous solution, and the time complexity of this approach is O(N log N).