## IPSC 2008

## Solution to Problem I – Inventing Test Data

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 N^{2} (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).