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
You can binary search for the earliest child that doesn’t form a cycle with their current MST.
Try to figure out why yourself.
Yeah, that worked just fine. Thanks!