This is my solution to coloring the graph (white & red) which I feel is simpler than the one given in the official editorial; but it boils down to the same thing. This is only for k=2. k=1 needs to be handled separately and is fairly straightforward. Solution:
That's it. How does this ensure all the constraints are satisfied? Correctness: Constraint  connectedness
Constraint  equal white and red nodes
Base Case: Leaf node, it is odd sized (size 1) and it has excess of its own color Consider subtree rooted at node u. Without loss of generality, assume it is white (W) Case  size(u) is even Split its children subtrees into even and odd. For every even child, there are equal number of W and R nodes. Now for odd children, it is easy to prove that there will be odd number of odd children. (n1/2) of the children have excess of W and (n+1/2) children have excess of R. Therefore, total W nodes (n1/2 + root_node) = total R nodes (n+1/2). Hence, for even sized subtree, W = R Case  size(u) is odd Again, split its children subtrees into even and odd. For every even child, equal number of W and R nodes. For odd children, you can prove that there will be even number of odd children. (n/2) of the children will have excess W and (n/2) of the children will have excess R, thus balancing the number of W and R in all the children. But, for the full subtree there will be an excess of W due to the root node. Hence, for odd sized subtree, W  R = 1 and that excess color is exactly the color of the respective root node. Hope it helps! Suggestions are welcome :) asked 14 Jan, 21:01

This is exactly same as my solution. :) Here is my code : My Solution answered 15 Jan, 10:43
