Stuck On JOI Inheritance

So, I’m doing JOI Inheritance (problem here, submission page here), and even though I understand the problem, I don’t know which algorithm to use. Is the intended solution some eldritch variation of Prim’s, or is it Kruskal’s?

I honestly don’t remember this problem but here’s my code + very brief solution notes in case it helps: https://github.com/thecodingwizard/competitive-programming/blob/master/JOI/JOISC%2015-inheritance.cpp


Shouldn’t this strategy TLE? There’s 3e5 edges and 1e4 children, so…

You can binary search for the earliest child that doesn’t form a cycle with their current MST.

Try to figure out why yourself.

1 Like

Yeah, that worked just fine. Thanks!