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

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?