Interesting puzzle ! The aim is more or less to find the best person to start spreading propagation of a message in a crowd of people. For this to be clearer let us introduce a little vocabulary :

- The
**eccentricity**of a vertex is the greatest distance between this vertex and any other vertex. - The
**radius**of a graph is the minimum eccentricity of any vertex, or the smallest distance at which can be one vertex from all the others. - The
**diameter**of a graph is the maximum eccentricity of any vertex, or the greatest distance between any pair of vertices. - The
**center**of a graph is the set of vertices of eccentricity equal to the radius (here the best person to start spreading the message).

In pratice, given a connected graph we want to compute its radius. Now, this puzzle is easiest as it seems, because we work not on all graphs, but only on **undirected trees**. Hence, we can rely on several properties.

First, there is only one simple path between 2 vertices of an undirected tree. As a consequence, the radius and diameter of such a tree are linked by the following relationship : **2R - 1 <= D <= 2R**. So instead of computing the radius, we can compute the diameter.

Moreover, any node can be the root of an undirected tree. It is useful to prove the correction of **an algorithm used to compute the diameter of an undirected tree in linear time**. The algorithm is the following.

- From any vertex s, find u one of the most distant vertex to s, by running a breadth first search. u is the node discovered last.
- Then run another BFS from u. If v is the vertex discovered last, then the distance between u and v is the diameter of the tree.

import java.util.*; import java.math.*; /** * This class is used to return both the last vertex encoutered, * and the excentricity of the starting vertex after a BFS */ class Result { public int length; public Node last; } /** * This class is representing a node of the graph. * neighbs is a list of the node neighbours * n is a unique constant id */ class Node { private ArrayList<Node> neighbs; private int n; public Node(int n){ this.n = n; neighbs = new ArrayList<Node>(); } public void add(Node n){ neighbs.add(n); } public ArrayList<Node> neighbs(){ return neighbs; } public int n(){ return n; } } class Solution { /** * Reads the standard input and constructs the graph to study * @return ArrayList of the vertices of the graph */ public static ArrayList<Node> readInfos() { Scanner in = new Scanner(System.in); ArrayList<Node> graph = new ArrayList<Node>(); int N, x, y; N = in.nextInt(); for (int i = 0; i < N; i++) { x = in.nextInt(); y = in.nextInt(); /*As node ids are consecutive and start from 0, when discovering a new node i, adds nodes to the graph until there are i+1 nodes */ while(graph.size() <= Math.max(x,y)) graph.add(new Node(graph.size())); graph.get(x).add(graph.get(y)); graph.get(y).add(graph.get(x)); } return graph; } /** * Runs a Breadth First Search and returns the last node encountered, * and the starting node excentricity * Complexity : O(|V|) * @param start starting vertex * @param graph graph to search * @return Result containing one of the most distant nodes from 'start', * and the distance between them*/ public static Result BFS (Node start, ArrayList<Node> graph) { Result res = new Result(); int[] depth = new int[graph.size()]; for (int i = 0 ; i < graph.size() ; i++) depth[i]=-1; depth[start.n()] = 0; Stack<Node> stack = new Stack<Node>(); stack.push(start); Node father, son; while (!stack.empty()) { father = stack.pop(); Iterator<Node> sons = father.neighbs().iterator(); while (sons.hasNext()) { son = sons.next(); if (depth[son.n()] == -1) { depth[son.n()] = depth[father.n()]+1; if (depth[son.n()] > res.length) { res.length = depth[son.n()]; res.last = son; } stack.push(son); } } } return res; } public static void main(String args[]) { ArrayList<Node> graph = readInfos(); Result r = BFS(graph.get(0), graph); r = BFS(r.last, graph); System.out.println((r.length+1)/2); } }