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.