As I understand, we should remember all the sons of a current node. To do it we should use either [40000][40000] or dynamic structures... We can't make DFS fast if we remember only fathers, am I right?

You are right. But we can store for each element his father, left son and right brother (3*40000) and DFS will be fast.

Good luck!

And what for should we store fathers? BTW, is 40000 functions enough for stack to get CRASH(STACK_OVERFLOW) on Test 4?

Edited by author 07.06.2005 20:43

I think that your DFS is bad. 40000 functions here must be OK. (And Test 4 should not be very large).

Yes. It turned out that I forgot to clear the zero element of the array. But now I've got WA12 :(

I got Ac.

You are wrong. If we remember parent for all vertex, we will can make DFS(in any kind) for O(n).
So, my program work more slow, but use only 794 kb.