Editorial for CCC '16 S3 - Phonomenal Reviews


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: FatalEagle

First, remove all vertices from the tree that are not a part of the vertex-induced subgraph formed from the Pho restaurants. This can be done with a breadth-first search from the leaves of the tree inwards, at each step adding all neighbors of the currently processing vertex that are not processed yet and are not Pho restaurants into the queue. This process does not change the answer for the problem, as those vertices will never be visited in the optimal solution. From here on, we will assume that all leaves of the tree are Pho restaurants (i.e. we must visit all the leaves at least once).

To visit all the leaves at least once, you must visit all vertices of the tree at least once. This is similar to a depth first search. If we add the condition that Jo should return to where she started, then no matter how Jo visits the vertices she will traverse each edge twice, taking exactly 2 \cdot (N-1) time. However, in the real problem, Jo does not have to return to her starting vertex. Therefore, there will be exactly one path in the tree where each edge is traversed once instead of twice (if there are edges not on this path that are traversed only once, then Jo must have somehow teleported between vertices, which is impossible). Obviously, to minimize the time Jo takes, we should maximize the length of such a path. This path is called the diameter of a tree. There are many ways to compute the diameter of a tree. The simplest way is to perform a depth first search from any vertex, find any of the farthest vertices from this vertex, then perform another depth first search from the vertex found in the first step. The distance between the vertices found at the end of both steps will be the diameter of the tree (proof is left as an exercise to the reader). Another way is to find the diameter recursively: the diameter is either in a subtree of the root, or it is formed by joining the two longest paths in different subtrees passing through the root. This method may be implemented in either \mathcal{O}(N) or \mathcal{O}(N \log N) (if sorting is used to find the two longest paths).

Complexity: \mathcal{O}(N) or \mathcal{O}(N \log N)


Comments


  • 2
    noYou  commented on March 14, 2020, 4:17 p.m.

    remove all vertices from the tree that are not a part of the vertex-induced subgraph formed from the Pho restaurants. This can be done with a breadth-first search from the leaves of the tree inwards, at each step adding all neighbors of the currently processing vertex that are not processed yet and are not Pho restaurants into the queue.

    What does this mean? I don't understand.