I can't imagine, how to solve this problem in 1 second. Please, help!

Just BFS two times.
First BFS:
>Start from any place
>>Then Find The one which you arrive at last.
Second BFS:
>Start from this place
>>Then the distance you go farthest is the Answer.

Edited by author 29.05.2004 08:49

I set its size to 50000, and got AC with 989K memory. But I suppose it needn't be so large. Who can tell me the upper bound of its size?

Edited by author 26.10.2004 15:37

I only used 325KB with BFS.

Edited by author 30.05.2005 18:21

First BFS:
Start from any place
Then Find The one which you arrive at last.
Second BFS:
Start from this place
Then the distance you go farthest is the Answer.

I don't understand why does it work?
First BFS may result many different place. Or last element of the queue? But wait how about the orders of the direction?

Second BFS
why?

I make tree rooted (parent info consumes only 1Mb - I store direction to the parent). Then for each node I find distance to deepest child (+4Mb). Then for each node I find 2nd maximum, the answer is max(max1+max2). It's general algo for any tree, and it worked here at around 0.093 sec.