Diameter And Radius Of A Tree

In Graph Theory, the diameter of a tree is the largest distance between any two points. The radius is the minimum distance of the maximum distance of any node on the of the diameter to one of the two diameter endpoints.

Take the following graph as an example.

In this case, the diameter is 14, from node 4 to node 5. The radius is 7, since min(max(7, 7), max(9, 5), max(14, 0)) is 7.

It is interesting to note that the optimal node to calculate the radius will always lie on the path of the diameter.

So, given a tree, how can we implement a program that could calculate both the diameter and the radius?

Let’s worry about the diameter first. To find it, we can start from an arbitrary node and run a depth-first search (DFS) to find the farthest node. Let this node be u. We can run another DFS from u to find the farthest node, and let this one be v. Then u and v must be the endpoints of the diameter. Next, we can simply traverse the path and calculate potential values for the radius along the way, and when we are done we have the final answer for the radius as well.

#include <bits/stdc++.h>
using namespace std;
const int MN = 5e5 + 5;
int n, e1, maxdist, parent[MN], dist[MN];
vector<pair<int, int>> adj[MN];
void dfs(int u, int p, int d){
    parent[u] = p;
    dist[u] = d;
    if (d > maxdist){
        maxdist = d;
        e1 = u;
    }
    for (auto [v, w] : adj[u]){
        if (v != p){
            dfs(v, u, d + w);
        }
    }
}
int main(){
    cin >> n;
    for (int i = 1, u, v, w; i < n; i++){
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    dfs(1, -1, 0);
    maxdist = 0;
    dfs(e1, -1, 0);
    cout << maxdist << "\n";
    int r = maxdist;
    for (int u = e1; parent[u] != -1; u = parent[u]){
        r = min(r, max(dist[u], maxdist - dist[u]));
    }
    cout << r << "\n";
}