Time complexity of this solution

Revision en2, by fmoeran, 2023-05-16 00:08:02

I really don't mean to bother anyone, this has just been annoying me for a good amount of time.

The problem is 835G. I seem to have a working solution but it's timing out at test 38.

I thought my solution worked in O(n) but it clearly either doesn't or something else is very wrong. My thought process was that both makeWanted and dfs should work in O(n) since there are no loops in a tree, so solve() should be O(n) as well.

I'd be incredibly thankful if you could have a look and see where I'm wrong :)

Tags time complexity, graphs, trees

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English fmoeran 2023-05-16 00:08:02 25
en1 English fmoeran 2023-05-15 23:35:26 658 Initial revision (published)