Divide the vertices into cycles connected by slides. All vertices within a cycle have the same maximum distance from any given vertex \(s\). Therefore, for each cycle, we need to efficiently manage the distance between any vertex in that cycle and the vertex furthest from it.

Consider the smallest subtree that contains all the vertices in the cycle. Such a subtree is unique. In this case, we can see that every leaf node in the subtree is a vertex included in the cycle. Given the properties of a tree, for any vertex \(u\) in the entire tree, the vertex in the subtree farthest from \(u\) is one of the endpoints \(v_1\) and \(v_2\) of that subtree’s diameter. Since the endpoints of a diameter are leaf nodes, both \(v_1\) and \(v_2\) belong to the cycle.

Consider a path leading to the farther of \(v_1\) and \(v_2\). There is a point that this path must pass through, which is the center of the subtree’s diameter. Because if the path does not pass the center, then the path leading to another end vertex of the diameter must be longer.

Therefore, the distance to the farthest vertex in the cycle can be decomposed into the sum of the distance to the center of the subtree’s diameter and the subtree’s radius. Since the length of the subtree’s radius is constant, we only need to carefully manage the sum of the distances to the centers of each subtree.

The center of a subtree can be a vertex or the midpoint of an edge. To handle this, we place an additional vertex at the midpoint of every edge. Now, the centers of all necessary subtrees are represented by vertices. We can now solve the problem by calculating the sum of distances between a set of vertices determined by the cycle and an arbitrary vertex \(u\) for all \(u = 1, 2, \ldots, N\). By applying rerooting technique, we can solve the problem in \({\cal O}(N \lg N)\).