Similar to shoom as well. Firstly, for each node, record all the “leaf children” (children with degree 1).
Next, start a DFS with a node, and a side. Recursively add children to opposite sides. Eventually, if the nodes are not equally distributed, then iterate on the smaller group, and for each vertex, try adding its leaf children (one by one) from the larger group to itself until the group sizes are the same.
@l_returns Yes, it can be proven that there is always enough leaves to move. Supose we call:
W: number of white nodes
R: number of red nodes
Wi and Wl: number of white internal nodes and number of white leaves, respectivily
Ri and Rl: number of red internal nodes and number of red leaves, respectivily.
Supose W>R. We need to prove that 2*Wl>=W-R (number 2 comes from the fact that a “move” changes the difference W-R 2 units).
So… W-R = Wi+Wl-(Ri+Rl) <= Wi+Wl-(Ri+Wi) == Wl-Ri <= Wl < 2Wl.
The easiest solution is my own. First, use preorder traversal for K=2 case. Assign one color to all the odd elements and another to all the even. What is important is that the first child of every node has a different color from the parent. The all other nodes would be able to find the opposing color by looking at its parent and the same color by looking at the first child of its parent.
Flips can be separately handled in separate DFS by maintaining a flipped array.
Actually, I think I can add something here.
What I did was, if answer was K=2, then do a simple DFS. In DFS, keeping assigning nodes one by one, first to U, then next to V, then next to U and so on.
I identified 4 cases, but they can be further reduced -
When the root of this fully colored subtree is in U and last colored leaf is also in U
When the root of this fully colored subtree is in V and last colored leaf is also in U
When the root of this fully colored subtree is in U and last colored leaf is also in V
When the root of this fully colored subtree is in V and last colored leaf is also in V
The intuition in cases was enough for me to give this approach a try. The proof I feel, is based on proving that the root node of subtree is connected either to its immediate next child, or to its grandchild (which in turn is connected its parent) in each of the 4 cases.
Did you mean “let W>=B and move enough W nodes to the right” (since W+B > R+G)? Just try it on many random trees and check the solutions. There must be some counterexample, since it produced WA.
Why do we assign color alternatively ?
Because we need to SAVE each and every edge from being deleted… So if We assign color in this way then all of the edges are kept as it is…
@l_returns
Sorry, my bad, that’s not true. Let’s try this. Split the internal nodes in fathers of a leave (Wf) and father of another internal node (Wo). Now,
W-R = Wo + Wf + Wl - (Ro + Rf + Rl) <= Wo+Wl-(Ro+Rf); because Wf<=Rl
Wo+Wl-(Ro+Rf) <= Wl; because Wo<=Ro+Rf (Wo is father of Ro’s and Rf’s)
Sorry that’s what I meant, I struggled with this for 2 days and couldn’t get why my solution did not work. Anyway I’ll just have to give up on it I guess