391. The Longest Walk in a Tree
The input is guaranteed to be a tree: connected, and with exactly n - 1
edges. Print its diameter, the number of edges on the longest path between any
two vertices.
The obvious approach is to run a breadth-first search from every vertex and take
the largest distance found. That is correct and it is O(n²), which is too
slow here.
There is a much better method and it is only two searches.
1. Search from any vertex, say vertex 1, and let a be a vertex at maximum
distance from it.
2. Search from a. The largest distance found is the diameter.
The claim behind step 1 is the interesting part: the farthest vertex from ANY starting point is always an endpoint of some longest path. Try it on the fifth test, where vertex 1 is in the middle and the answer is 4 rather than the 2 a single search from vertex 1 reports.
Constraints - `1 ≤ n ≤ 100000` - `m = n - 1` - The input is always a tree: connected and without cycles.
Input
The first line contains two integers n and m, the number of vertices and
edges. Each of the next m lines contains two integers u and v, an
undirected edge between those vertices. Vertices are numbered 1 to n.
Output
Print one integer, the diameter of the tree.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.