I came across this problem from the CCDSAP page. My approach is to apply BFS twice:

- BFS on a random node (0). Noting the farthest point u.
- BFS on u. This gives me diameter of the tree.

Answer is (diameter+1)/2. I got AC already through a DFS based implementation of the same idea.

Problem URL: https://www.spoj.com/problems/GCPC11J/

My solution: http://ideone.com/xoFg2v

I’m surprised as the time limit of ~1.8 seconds should be sufficient to run BFS twice (N = 10^5) and the editorials online suggest the same approach.