Count nodes within K-distance from all nodes in a set

Question

The problem is - Given an undirected tree with some marked nodes in a set and a positive number K. We need to print the count of all such nodes which have distance from all marked nodes less than K.

My first approach-

I ran bfs on every from each marked node given in the set and takes the intersection of the respective answers. The time complexity of this solution if there are m notes in the set would be O(m*(V+E)). Can it be further optimized ?

My second approach-

If I find two nodes from set which are maximum distance from each other, I can say that all the nodes which are a distance less than k from these two nodes will also be at a distance less than k from other marked nodes in the set. Now, I have to apply bfs at only those two extreme nodes. But, the problem is How to find two nodes from set which are maximum distance from each other? I can only think of floyd warshall over here but that would be O(V^3).

What would be the most optimal solution to this problem?

Answer 1

Add a new node(let's say s) and connect it to all the marked nodes in the set. Then, find all the nodes which are at a distance less than k+1 from s and subtract number of marked nodes from it. T(n)=O(V+E)

In the second approach, we can actually find the two nodes (let's say uand v) with maximum distance between them in O(V+E). How do we find those vertices? Pick a vertex w and place it in a queue. While the queue is non-empty add the neighbors of the next vertex in the queue to the end of the queue. When the queue is empty, take note of the most recently removed vertex. This will be u. Perform the procedure again and you will have v. Check this link for proof. https://stackoverflow.com/questions/9951363/finding-the-root-that-minimize-tree-depth