Here is the problem: [problem:1790F]↵
↵
Here is the idea behind the solution: We add black nodes to the tree one by one, each time calling a BFS starting on the newly added black node in order to find the closest black node. If the path we find is smaller than the previous answer, we update accordingly. I also implemented an optimization where if the BFS depth exceeds the previous smallest path length, we stop the BFS.↵
↵
My question is why / in what type of test case does this TL? I tried some randomized tests on $2\cdot10^5$ nodes but couldn't find a TL.↵
↵
Here is my implementation of said solution: [submission:191442467]
↵
Here is the idea behind the solution: We add black nodes to the tree one by one, each time calling a BFS starting on the newly added black node in order to find the closest black node. If the path we find is smaller than the previous answer, we update accordingly. I also implemented an optimization where if the BFS depth exceeds the previous smallest path length, we stop the BFS.↵
↵
My question is why / in what type of test case does this TL? I tried some randomized tests on $2\cdot10^5$ nodes but couldn't find a TL.↵
↵
Here is my implementation of said solution: [submission:191442467]
