Diverse Coloring
Contest: VK Cup 2022 - Отборочный раунд (Engine)
Difficulty rating: 3200
Tags: constructive algorithms, trees

In this problem, we will be working with rooted binary trees. A tree is called a rooted binary tree if it has a fixed root and every vertex has at most two children.

Let's assign a color — white or blue — to each vertex of the tree, and call this assignment a coloring of the tree. Let's call a coloring diverse if every vertex has a neighbor (a parent or a child) colored into an opposite color compared to this vertex. It can be shown that any tree with at least two vertices allows a diverse coloring.

Let's define the disbalance of a coloring as the absolute value of the difference between the number of white vertices and the number of blue vertices.

Now to the problem. Initially, the tree consists of a single vertex with the number $$$1$$$ which is its root. Then, for each $$$i$$$ from $$$2$$$ to $$$n$$$, a new vertex $$$i$$$ appears in the tree, and it becomes a child of vertex $$$p_i$$$. It is guaranteed that after each step the tree will keep being a binary tree rooted at vertex $$$1$$$, that is, each vertex will have at most two children.

After every new vertex is added, print the smallest value of disbalance over all possible diverse colorings of the current tree. Moreover, after adding the last vertex with the number $$$n$$$, also print a diverse coloring with the smallest possible disbalance as well.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the final tree.

The second line contains $$$n-1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i \le i - 1$$$) — the numbers of parents of vertices $$$2, 3, \ldots, n$$$. No integer appears more than twice among $$$p_2, p_3, \ldots, p_n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print $$$n-1$$$ integers — the smallest value of disbalance over all possible diverse colorings of the tree after adding vertices $$$2, 3, \ldots, n$$$.

Then print a string of $$$n$$$ characters 'w' and 'b', describing a diverse coloring with the smallest possible disbalance for the whole tree after adding vertex $$$n$$$: the $$$i$$$-th character must be equal to 'w' if vertex $$$i$$$ is colored white, and 'b' if it's colored blue. The absolute value of the difference between the numbers of 'w' and 'b' characters must be equal to the last printed integer. Each vertex must have a parent or a child colored into the color opposite to the vertex's color.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, examples of diverse colorings with the smallest possible disbalances for all intermediate trees are illustrated below:

Example input:
2
7
1 2 2 1 5 5
8
1 2 3 4 5 6 7

Example output:
0
1
2
1
0
1
wbwwwbb
0
1
0
1
0
1
0
wbwbwbwb

Editorial:
It turns out that it is always possible to construct a diverse coloring with disbalance $$$0$$$ or $$$1$$$ (depending on the parity of $$$n$$$), except for the case of a tree with $$$4$$$ vertices with one vertex of degree $$$3$$$ (which is given in the example).
Let's traverse the tree from bottom to top. For each subtree, we will try to construct a diverse coloring where the subtree root is colored white. We will define the disbalance of the subtree coloring to be the number of vertices colored white, minus the number of vertices colored blue. This is equivalent to the original definition, except that now the number also has a sign.
We will aim at obtaining disbalances $$$0$$$ and $$$+1$$$, if possible. In some small cases, it will be impossible. We will say "subtree has disbalance $$$x$$$" or "vertex has disbalance $$$x$$$", meaning that we have constructed a coloring of the (vertex's) subtree with disbalance $$$x$$$.
Let $$$u$$$ be the root of the subtree (colored white):
• If $$$u$$$ has no children, the only coloring has disbalance $$$+1$$$; however, it is not diverse. Thus, we will have to be careful about the leaf case in the future.
• If $$$u$$$ has one child $$$v$$$, flip the colors in $$$v$$$'s subtree to create a blue neighbor for $$$u$$$:   If $$$v$$$ had disbalance $$$0$$$ before the flip, now $$$u$$$ has disbalance $$$+1$$$.  If $$$u$$$ had disbalance $$$+1$$$ before the flip, now $$$u$$$ has disbalance $$$0$$$.
• If $$$v$$$ had disbalance $$$0$$$ before the flip, now $$$u$$$ has disbalance $$$+1$$$.
• If $$$u$$$ had disbalance $$$+1$$$ before the flip, now $$$u$$$ has disbalance $$$0$$$.
• If $$$u$$$ has two children $$$v$$$ and $$$w$$$:   If both have disbalance $$$0$$$, flip the colors in at least one of $$$v$$$'s and $$$w$$$'s subtrees, now $$$u$$$ has disbalance $$$+1$$$.  If both have disbalance $$$+1$$$, flip the colors in either $$$v$$$'s or $$$w$$$'s subtree, now $$$u$$$ has disbalance $$$+1$$$.  If one has disbalance $$$0$$$ and the other has disbalance $$$+1$$$, flip the colors in the one with $$$0$$$, now $$$u$$$ has disbalance $$$0$$$.
• If both have disbalance $$$0$$$, flip the colors in at least one of $$$v$$$'s and $$$w$$$'s subtrees, now $$$u$$$ has disbalance $$$+1$$$.
• If both have disbalance $$$+1$$$, flip the colors in either $$$v$$$'s or $$$w$$$'s subtree, now $$$u$$$ has disbalance $$$+1$$$.
• If one has disbalance $$$0$$$ and the other has disbalance $$$+1$$$, flip the colors in the one with $$$0$$$, now $$$u$$$ has disbalance $$$0$$$.
The only issue happens when $$$u$$$ has two children that are both leaves: we have to recolor both $$$v$$$ and $$$w$$$ into blue, which will force $$$u$$$ to have disbalance $$$-1$$$. Let's add new cases to the analysis above based on the existence of subtrees with disbalance $$$-1$$$:
• If $$$u$$$ has one child $$$v$$$ with disbalance $$$-1$$$:   Flip the colors in $$$v$$$'s subtree, now $$$u$$$ has disbalance $$$+2$$$.
• Flip the colors in $$$v$$$'s subtree, now $$$u$$$ has disbalance $$$+2$$$.
• If $$$u$$$ has two children $$$v$$$ and $$$w$$$, where $$$v$$$ has disbalance $$$-1$$$:   If $$$w$$$ has disbalance $$$-1$$$, flip the colors in either $$$v$$$'s or $$$w$$$'s subtree, now $$$u$$$ has disbalance $$$+1$$$.  If $$$w$$$ has disbalance $$$0$$$, flip the colors in $$$w$$$'s subtree, now $$$u$$$ has disbalance $$$0$$$.  If $$$w$$$ has disbalance $$$+1$$$, flip the colors in both $$$v$$$'s and $$$w$$$'s subtrees, now $$$u$$$ has disbalance $$$+1$$$.
• If $$$w$$$ has disbalance $$$-1$$$, flip the colors in either $$$v$$$'s or $$$w$$$'s subtree, now $$$u$$$ has disbalance $$$+1$$$.
• If $$$w$$$ has disbalance $$$0$$$, flip the colors in $$$w$$$'s subtree, now $$$u$$$ has disbalance $$$0$$$.
• If $$$w$$$ has disbalance $$$+1$$$, flip the colors in both $$$v$$$'s and $$$w$$$'s subtrees, now $$$u$$$ has disbalance $$$+1$$$.
We can see that, once again, a new case appears where a subtree has disbalance $$$+2$$$ (described at the beginning of this tutorial), and unfortunately we can't avoid that. We can see that this case only happens for a specific subtree of $$$4$$$ vertices. Let's proceed with the case analysis...
• If $$$u$$$ has one child $$$v$$$ with disbalance $$$+2$$$:   Flip $$$v$$$'s color (not the whole subtree, but just $$$v$$$), now $$$u$$$ has disbalance $$$+1$$$.
• Flip $$$v$$$'s color (not the whole subtree, but just $$$v$$$), now $$$u$$$ has disbalance $$$+1$$$.
• If $$$u$$$ has two children $$$v$$$ and $$$w$$$, where $$$v$$$ has disbalance $$$+2$$$:   If $$$w$$$ has disbalance $$$-1$$$, flip the colors in both $$$v$$$'s and $$$w$$$'s subtrees, now $$$u$$$ has disbalance $$$0$$$.  If $$$w$$$ has disbalance $$$0$$$, flip $$$v$$$'s color, now $$$u$$$ has disbalance $$$+1$$$.  If $$$w$$$ has disbalance $$$+1$$$, flip $$$v$$$'s color and the colors in $$$w$$$'s subtree, now $$$u$$$ has disbalance $$$0$$$.  If $$$w$$$ has disbalance $$$+2$$$, flip the colors in either $$$v$$$'s or $$$w$$$'s subtree, now $$$u$$$ has disbalance $$$+1$$$.
• If $$$w$$$ has disbalance $$$-1$$$, flip the colors in both $$$v$$$'s and $$$w$$$'s subtrees, now $$$u$$$ has disbalance $$$0$$$.
• If $$$w$$$ has disbalance $$$0$$$, flip $$$v$$$'s color, now $$$u$$$ has disbalance $$$+1$$$.
• If $$$w$$$ has disbalance $$$+1$$$, flip $$$v$$$'s color and the colors in $$$w$$$'s subtree, now $$$u$$$ has disbalance $$$0$$$.
• If $$$w$$$ has disbalance $$$+2$$$, flip the colors in either $$$v$$$'s or $$$w$$$'s subtree, now $$$u$$$ has disbalance $$$+1$$$.
It follows that for any other tree, except two special cases of a $$$3$$$-vertex tree and a $$$4$$$-vertex tree, it is possible to obtain disbalance $$$0$$$ or $$$+1$$$.
From this point, one way to implement the solution is to carefully consider all the cases. Note that whenever we say "flip the colors in $$$v$$$'s subtree", we can just set some flag in vertex $$$v$$$. Then, as we traverse the tree from top to bottom, we can construct the correct coloring in $$$O(n)$$$ time.
Another way is to use dynamic programming f(u, d, hasNeighbor) = true/false: whether it is possible to color $$$u$$$'s subtree to obtain disbalance $$$d$$$ so that all vertices except $$$u$$$ have neighbors of opposite color, and $$$u$$$ has such a neighbor iff hasNeighbor = true. Since it is enough to limit disbalance by $$$O(1)$$$, we can conclude that the number of states, the number of transitions, and the time complexity are all $$$O(n)$$$.