PROBLEM LINKS:
DIFFICULTY:
Easy-Medium
PREREQUISITES:
trees, dfs, diameter
SOLUTION:`
Clearly, the input is a forest, and in some subtasks we have an additional restriction that the components are simpler (paths in subtask 1, at most 2 vertices per component in subtask 4).
Terminology: Eccentricity of a vertex is the distance from this vertex to the farthest other vertex. E.g., in the example graph on page 1 of the statement, the eccentricity of vertex 1 within its component is 10. The center of a tree is a vertex with the smallest eccentricity. (Note that sometimes a tree can have two centers.) Given a tree with x vertices, we can find its center in O(x) time: for example, find a longest path, and then the center is the vertex (or two vertices) that are closest to its middle (distance-wise). In a tree with two centers we will pick one arbitrarily and call it the center.
There is always a pretty simple optimal solution:
In each component, find its center.
Connect the center with maximum eccentricity to each of the other centers.
Below I prove why this always works.
First, consider the case when there are only two components A and B; that is, m=n-2. (These are the cases worth 47 points.) Suppose that the edge you add joins vertex x in A and vertex y in B. The diameter of the new tree is the maximum of three values:
diameter(A)
diameter(B)
eccentricity(x) + eccentricity(y) + L
(Here and everywhere below, eccentricity(x) is the eccentricity of x within its original component A. The “+L” at the end is the length of the new edge between x and y.)
We cannot change the two original diameters, we can only make the last distance as small as possible by choosing x and y to be the centers of A and B, respectively. That is clearly optimal.
Now for the general case with multiple components. Again, the answer is at least the maximum of their diameters, and we cannot influence this. To be certain that we are optimal, we just need to minimize the maximum of distance(u,v) where u,v belong to different components.
Suppose that we already know an optimal set S of (n-m) edges to add. For each pair of components A and B, let xy be the unique path that connects them, with x belonging to A and y belonging to B. The maximum distance for these two components is currently equal to eccentricity(x) + length(x,y) + eccentricity(y). Note that length(x,y) is at least L times the number of new edges on xy.
Now let’s change S into S’ as follows: For each component, find its center. Whenever S contained an edge between components A and B, S’ will contain an edge between their centers. It should now be obvious that the maximum distance for S’ is at most equal to the maximum distance for S: this is because for any two components we improved or kept equal all three parts of their distance:
If x’ is the center of A and y’ is the center of B, then eccentricity(x’)<=eccentricity(x), and the same holds for y’ versus y.
The path between x’ and y’ in the graph where we added the edges from S’ contains the same number of new edges as the path between x and y when using edges from S – because it visits the same components as in the original graph, in the same order. Additionally, the xy path in the new graph contains no other edges.
Thus, right now we know that there is always an optimal solution where each new edge connects the centers of two components. The last thing we need to determine is the order in which we shall connect them.
Suppose that we have at least three components. Let’s label three of their centers x, y, and z in such a way that eccentricity(x) >= eccentricity(y) >= eccentricity(z) >= eccentricity of any other center.
Clearly, the answer is at least eccentricity(x)+L+eccentricity(y), because we have to connect the first two components somehow and this is the best we can do. Also, it is impossible to connect each pair of x, y, and z directly, because that would form a cycle. Hence, two of them have to be connected via another center. The best we can do is to choose y and z as those two. Then, their distance is at least eccentricity(y)+2L+eccentricity(z).
And now we are done, because now we can easily verify that when we connect x directly to each other center, the maximum distance over all pairs of components is as small as it can possibly be.
source : http://www.quora.com/What-is-the-solution-for-Dreaming-on-IOI-2013/answer/Michal-Forišek
EDITORIALIST’S SOLUTION:
Can be found here.