Observations, Invariants and Constructive Algorithms.
Given a tree G with N (N is even) number of nodes, we can make Graph H_k by adding an edge between every pair of nodes which have distance up to k. We need to find the minimum k such that we can split all nodes into two disjoint partitions of size N/2 such that if considering the edges of the graph H_k having both ends in different partitions, all the nodes are connected. Also, print one such valid bipartition.
Note: I shall use the color white to represent a node in the first partition while red to represent a node in the second partition.
SUPER QUICK EXPLANATION
- It is always possible to find a bipartition with k = 2 such that all the nodes are connected.
- The idea is, that for each node, we need to color nodes in the subtree of this node in a manner such that |W-R| \leq 1. To be precise, if the number of nodes in the subtree of a node is odd, |W-R| = 1, Otherwise W == R where W and R denote the number of white and red nodes respectively.
- To ensure that the resulting bipartitions are connected, each non-leaf node shall have a child of opposite color.
- Corner case is when it is possible to find bipartitions of the tree itself with k = 1. It happens when the number of vertices at odd depth is the same as the number of vertices at even depth, both of them being N/2. This case can be handled separately.
For k = 1. The only possible bipartition which is connected is the one where nodes with odd depth are colored white while nodes at even depth are colored red. But the number of white and red nodes may not be equal. So, for the trees where the number of nodes at odd depth is same as the number of nodes at even depth, we can directly print this bipartition with k = 1.
For rest cases, we need k \geq 2. It can be proven that k = 2 is sufficient for any tree.
Lemma: Nodes in Graph H_2 can always be colored white and red such that considering edges with opposite colored ends only, all nodes are connected.
Proof: We shall prove it subtree wise, by the principle of induction. We shall maintain the following invariants.
- We shall maintain an invariant that for node u if the number of nodes in the subtree of u is odd, number of white nodes excluding node u is same as the number of red nodes, otherwise, number of white nodes is precisely same as the number of red nodes when node u is included.
- Every non-leaf node has at least one opposite colored node as its direct child.
Considering the base case, where node u is a leaf, we can simply color it white, thus invariant is maintained.
Now, If a node has only one child, let us color the node as opposite of its child node. It can be seen that the first invariant automatically holds here.
Now assuming all the children of node u maintain this invariant, let us prove that we can maintain this invariant for node u too.
Considering children of u, the ones having even subtree size. We know that the number of white nodes in its subtree is the same as the number of red nodes, while the ones having odd subtree size, have exactly one colored node more. We first need to flip the color of subtrees of some children, until the absolute difference between the number of white and red colored nodes is minimum.
An important point to note is, that we can flip subtree at node u without breaking any invariant. If the node has even subtree size, the number of white and red nodes isn’t affected, while if subtree size is odd, the number of one colored node increases by 1 and other colored node decreases by 1, thus causing the absolute effect of 2 nodes. So, It makes sense to flip subtrees with odd subtree size, till the minimum is achieved.
Now, if subtree size of node u is even, node u shall be colored to make the number of white nodes same as the number of red nodes since absolute difference after flips would be 1. Otherwise, we can color node u any color, but before that, we need to balance white and red nodes in the subtree of u excluding u, which can be achieved using flips.
To maintain the second invariant, we can find one child with even subtree size and if required, flip it to ensure it has opposite color as node u. If no child has even subtree size, the second invariant is automatically holding. You can prove it easily.
Hence, this proves by induction that it is possible to maintain these two invariants which not only ensure the existence of valid bipartitions but also give one valid bipartition.
Flips can be separately handled in separate DFS by maintaining a flipped array.
After handling cases, Implementation shall be easy, which can be referred in solutions below.
Time complexity is O(N) per test case.
AUTHOR’S AND TESTER’S SOLUTIONS:
Feel free to Share your approach, If it differs. Suggestions are always welcomed.