CHEFCOMP optimization

I was trying to optimize the question chefina and strange tree of the recent long challenge.
My naive approach was doing DFS for each vertex in the permutation and afterwards removing it from the adjacency list of the graph.
This was accepted for the first subtask but due to O(N²) time was not getting accepted for the other subtasks.
Could anyone help in optimization ?
I was thinking along the lines of doing a reverse DSU for the graph but couldn’t formulate something good…

1 Like

See the Editorial of CHEFCOMP.
(CHEFCOMP - Editorial)

Yes thanks, it came a bit late that’s why.