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.
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.