Count nodes within K-distance from all nodes in a set
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