Trick to compute linearization times for trees

Revision en1, by The-Winner, 2025-12-26 16:36:40

Hello.

I've just thought of a way to compute the linearization times (entry and exit) for a tree given by "the father of node $$$i$$$ is $$$p_i$$$ ($$$p_i \lt i$$$)" without the usual graph creation. This might improve the time of a submission (you no longer do push_backs) but I haven't tested. This is very niche (the number of problems where the tree is given in this way is small and those where you don't need the actual graph are even fewer) so feel free to ignore the blog.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English The-Winner 2025-12-26 17:15:42 13 (published)
en5 English The-Winner 2025-12-26 17:14:27 25
en4 English The-Winner 2025-12-26 17:13:20 345
en3 English The-Winner 2025-12-26 17:08:28 248
en2 English The-Winner 2025-12-26 17:04:26 1124
en1 English The-Winner 2025-12-26 16:36:40 524 Initial revision (saved to drafts)