So I’ve solved this problem, but I’m having some trouble understanding how a win is guaranteed is k^2 \geq n.
I understand that the proof in the official editorial follows a greedy strategy in which they always cut off the node that leads to the earliest fork, but this part is really confusing:

Consider a star-like tree with N=401 and 20 branches of length 20. You can check that n_r=(20-r)^2 for this graph, and that the game ends in 20 marks by Daniel and 19 moves by Stjepan.