For data:5 5 4 5 1
I know it's illegal according to the statement,but it's the only one I can find now. However,I believe there is an "legal" one which may make some AC prog wrong ans!
My AC prog says 5 4! I used bfs twice,and I didn't sort the 2 numbers! Perhaps there is no data figures out this problem.
btw,I fixed my prog at once.Sorry for my poor English.

Edited by author 06.08.2009 14:41

Edited by author 06.08.2009 14:47

Sorry,but now I know maybe there isn't a "legal" data that makes error.
I can't prove it well,but it's true:when use 2bfs,you needn't sort 2 num.
See:
Divide the tree into 2 parts,L and R.
The answer,if 2 num,must be in the longer part.Let's say it's on the right.
First you bfs to right,then bfs to leftmost.
When you follow the longest chain back again,you are going to right side.
If the data is legal,part R is in inscend(I don't know how to spell) order.So ans num1<ans num2.
so you needn't sort them at all!