Editorial for Bubble Cup V9 C Paint it really, really black
Submitting an official solution before solving the problem yourself is a bannable offence.
Root the tree at node . Now notice that if we had a function
such that
colors the whole subtree of node
black (except maybe
itself) and returns us to
in the process, we can easily solve the problem. Let
be the parent of
. Then after entering
do
. If
is black, go to
and never return to that subtree again. Otherwise, go from
to
then to
then to
. Now
is black and we can continue to do the same for other children of
and so on.
Now it is easy to see that all that we need to do is to make DFS-like tour of the tree and upon returning from a node to a corresponding parent we check the color of the child node. If it is black, continue normally, otherwise visit it again and again return to the parent and then continue normally. The only exception is the root node as it has no parent. After finishing the tour and ending up in node , if it is black, we are done. If not, it is the only pink one and we can select any child
of
and do
. Now all nodes are black.
It is recommended to do the implementation with a stack. Complexity is .
Comments