I also tried to use dp in bfs layers but a lot of problems arise. I don’t know how you managed to make it passed but I couldn’t.

First , seeing your code, you are just runing a bfs from the first root the you find. But then, the maximum size of the queue can be 2 \times \sqrt N. So K can be roughly 27 in worst case.

Imagine something like this:

The number 1 is your root for BFS. The second layer will have 1 node , the third layer will have 3 nodes, then 5 and so on. If the maximum number of nodes is 200, then your last layer will have 27 nodes.

Try this input : https://ideone.com/95BxyF

It will make you to use 2^27 * 197 of memory and your code will fail.

I managed to “solve” this situation doing this : Simulate the BFS with every node as a root and pick the one that minimize the maximum size of the BFS queue. I think it can be proof that with this approach the maximum size is at most 19 (or maybe 15), because I think K can be also bigger than the maximum size of the bfs queue.

But even with that I couldn’t make it passed the testcases.

By the way, hats off to you , @carre . Amazing problem and editorial