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.