We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
O(N) time and O(N) space solution, passes all test cases and does not use recursion:
The basic idea is that we compute a minimum spanning subtree, e.g. the smallest subtree that spans all the cities that we need to deliver letters to. This can be done in O(N) time by putting all non-letter degree-1 cities in a queue, then repeatedly "pruning" them (e.g. ticking them off in a bit mask), then whenever we detect a parent that is also non-letter and has degree 1, we add it to the queue. The final resulting subtree has no leaves which are non-letter cities, and also contains all letter cities, so by definition is the "minimum spanning subtree". Note this is not related to the standard minimum spanning tree algorithm.
Once we have a bitmask telling us which nodes are in the subtree, we find the diameter of the subtree using two Breadth first searches, as explained here (though that thread is for weight-1 edges, it is straightforward to generalize to arbitrarily weighted edges: simply keep track of all distances from the source while you are BFSing). Finally, the answer, e.g. the minimum distance needed to travel to cover the entire subtree, is just twice the total weight of that subtree minus the diameter.
Jeanie's Route
You are viewing a single comment's thread. Return to all comments →
O(N) time and O(N) space solution, passes all test cases and does not use recursion:
The basic idea is that we compute a minimum spanning subtree, e.g. the smallest subtree that spans all the cities that we need to deliver letters to. This can be done in O(N) time by putting all non-letter degree-1 cities in a queue, then repeatedly "pruning" them (e.g. ticking them off in a bit mask), then whenever we detect a parent that is also non-letter and has degree 1, we add it to the queue. The final resulting subtree has no leaves which are non-letter cities, and also contains all letter cities, so by definition is the "minimum spanning subtree". Note this is not related to the standard minimum spanning tree algorithm.
Once we have a bitmask telling us which nodes are in the subtree, we find the diameter of the subtree using two Breadth first searches, as explained here (though that thread is for weight-1 edges, it is straightforward to generalize to arbitrarily weighted edges: simply keep track of all distances from the source while you are BFSing). Finally, the answer, e.g. the minimum distance needed to travel to cover the entire subtree, is just twice the total weight of that subtree minus the diameter.