Finding the node with the smallest maximum distance to all the other nodes
It's not about constant optimizations. It's all about a more efficient algorithm. Here is a simple observation: the given graph is always a tree(because it has exactly n - 1 edges)(if it is not a tree, it is not connected and it is not clear what the answer is(maybe +infinity), so I will assume that it is a tree). That's why we can use the following algorithm:


Pick an arbitrary vertex v.
Find the furthest vertex from v(let's call it u).
Find the furthest vertex from u(let's call it t).
The distance between u and t is the answer.


This solution requires only two breadth-first searches so it has a linear time complexity. Why is it correct? I will not post a formal proof here, but drawing several trees on paper should help you to understand it. It is important that a given graph is a tree(this algorithm does not work for arbitrary graphs).

This algorithm actually finds a diameter of a tree, but it is easy to solve the original problem when a diameter is found. We can just pick the center of the diameter. To do it, we can find the path from u to t(it requires a small modification in bfs: we also need to keep track of a parent for each vertex) and store in a list. After that we just need to get the middle element of the list. If the number of elements in the list is even, we can pick any of two middle elements.