SPOJ - GCPC11J - Getting unexpected TLE verdict

help
1

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

  1. BFS on a random node (0). Noting the farthest point u.
  2. 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: SPOJ.com - Problem GCPC11J
My solution: xoFg2v - Online C++0x Compiler & Debugging Tool - Ideone.com

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.