Need help with Codechef Minimum Subtree Cover Problem

Revision en1, by elementaryGuy, 2021-06-14 17:30:04

Hello CodeForces! I Need help with SUBTRCOV problem.

My thought process until now :

- The optimal set always consists of 1-degree nodes

  - Initially we start with a single 1-degree node as the subtree cover

  - Now in each step, if the subtree formed by the current subtree cover has less than k nodes, then we select farthest node from the current subree and add it to the cover.

However I can't think of efficient way of finding the farthest node (my approach involves using dfs everytime to find the farthest node which is O(n)) and hence my solution is O(n^2). Any help will be much appreciated. Thanks in advance.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English elementaryGuy 2021-06-14 17:30:04 782 Initial revision (published)