Why there so strict timelimit.
I solved this problem in OpenCup (where LT is 2 s). But for solve it there I need to make some optimization. Is it possible to increse timelimit to 2sec ?

My solution is O(NlogN).

Edited by author 01.04.2008 15:17

I also needed some minor optimizations to pass 1616 here which was accepted in OpenCup.

AC 0.078 sec.

vector< vector<int> > and vector<int> get to big time ...

I just delete edges with O(NlogN), but I understand how to do it with O(N). But I know O(M) solution for general but this solution don't use that we work with "cactus", I used it so have O(NlogN) solution.

Who can tell me How to solve with O(n)?

Just one DFS - 0.171 sec. even on vector<int> g[50000]

Could somebody provide some tricky test cases?

Edit: Or maybe provide TC 3 or 10?

Edited by author 17.04.2011 09:46

can you give me some tests i've got 'wrong answer' for several times,
thank you very much!