Editorial for TLE '16 Contest 4 P4 - Christmas Tree Building

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ZQFMGB12

For the first subtask, we note that to get the maximum height tree, we connect all of the tree parts into a straight line. Thus, the answer is equal to the single edge's cost plus the number of additional connections (N-2). For the minimum height tree, we will connect all of the unconnected tree parts to a single node that is part of the edge given. Thus, the answer is equal to the length of the edge.

Time complexity: \mathcal{O}(1)

For the second subtask, we note that the structure is already connected to form a tree, and thus, is static.

We first run an all-pairs shortest path algorithm, such as a BFS/DFS starting from each node, or Floyd-Warshall. Note that even though the graph is weighted, we can still use a BFS since the graph is a forest. For the maximum height, we simply find the longest path from one node to any other node in the tree. For the minimum height, we need to find the minimum longest path starting from each node.

Time complexity: \mathcal{O}(N^2) or \mathcal{O}(N^3)

For the third subtask, we use the same algorithm presented in subtask 2 to every single connected component in the forest. The difference is that now, we need to connect the trees together.

For the maximum case, we should connect the ends of all of the tree diameters together.

For the minimum case, we should connect all of the connected components to the component with the largest radius and thus, the answer is the largest radius. If there are two or more components with the largest radius, we must increase our answer by 1.

Time complexity: \mathcal{O}(N^2) or \mathcal{O}(N^3)

For the fourth subtask, we need an efficient method of finding the diameter of a tree. The diameter of a tree can be found by first running a BFS on any node and then another BFS starting from the last node of the previous BFS. The furthest distance found on the second BFS is the tree diameter.

Time complexity: \mathcal{O}(N)

For the fifth subtask, we need an efficient method of finding the radius of a tree. One way to accomplish this is to run DFS twice on each component. For both of the DFSes, we will start from a root node, which is chosen arbitrarily. Then, for the first DFS, find the length of the longest two paths starting from each node to the leaves of the tree. For the second DFS, each node will now consider if its longest path includes its parent. If the current node is not on the parent's longest path, then we check if the parent's longest path plus the edge in between is the largest or the second largest compared to the paths we have already computed for the current node. If the current node is on the parent's longest path, we use the parent's second longest path instead.

Alternatively, we can find the radius by simply finding the diameter of each tree, using the same method presented in the fourth subtask, and finding the most even split of each diameter.

Time complexity: \mathcal{O}(N)

Comments


  • 0
    StillHungry  commented on Dec. 26, 2016, 6:13 p.m.

    Hi,Can someone please describe the algorithm (in a bit detail) used in Last Case i.e. finding center in case of weighted tree ... Unfortunately I could not find a good resource :( ........ Thanks in advance :)


    • 1
      Zander  commented on Dec. 26, 2016, 6:16 p.m. ← edited

      You can find the middle of the longest path (I did it by keeping track of all nodes along the longest path then checking every single one but thats super sketchy)


      • 0
        StillHungry  commented on Dec. 27, 2016, 1:07 a.m.

        Thanks for the reply Zander ...But Can someone explain what happens in second DFS of the author's algorithm ,,,I simply do not get it...Thanks in advance :)


        • 2
          ZQFMGB12  commented on Dec. 27, 2016, 1:52 a.m.

          For the second DFS, we consider if a node's longest or second longest path goes through its parent rather than its children.


  • 1
    defaq  commented on Dec. 25, 2016, 9:28 a.m. ← edit 2

    IOI 2013 Day 1 Problem 1


    • 3
      ZQFMGB12  commented on Dec. 25, 2016, 2:27 p.m.

      Actually, while writing the problem, I noted that while the problem is similar to Dreaming, it is intended to be easier since you want to maximize/minimize the radius rather than the diameter.