CF1781G.Diverse Coloring

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.

本题中，我们将处理有根二叉树。若一棵树具有固定的根节点，且每个顶点至多有两个子节点，则称其为有根二叉树。

我们为树的每个顶点赋予一种颜色——白色或蓝色，并称这种赋色方式为树的一种着色。若树的每个顶点均存在一个邻居（父节点或子节点）与其颜色相反，则称该着色为多样着色（diverse coloring）。可以证明：任意含至少两个顶点的树均存在多样着色。

我们定义一种着色的不平衡度（disbalance）为白色顶点数与蓝色顶点数之差的绝对值。

现在进入题目主体部分：初始时，树仅包含一个编号为 $1$ 的顶点，它即为树的根节点。随后，对每个 $i$ 从 $2$ 到 $n$，向树中添加一个新顶点 $i$，并使其成为顶点 $p_i$ 的子节点。保证在每一步操作后，树仍是以顶点 $1$ 为根的二叉树，即每个顶点至多有两个子节点。

每次添加一个新顶点后，请输出当前树在所有可能的多样着色中所能达到的最小不平衡度。此外，在添加完编号为 $n$ 的最后一个顶点后，还需额外输出一种达到最小可能不平衡度的多样着色方案。

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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——表示最终树中顶点的数量。

第二行包含 $n-1$ 个整数 $p_2, p_3, \ldots, p_n$（$1 \le p_i \le i - 1$）——分别表示顶点 $2, 3, \ldots, n$ 的父节点编号。在 $p_2, p_3, \ldots, p_n$ 中，任意整数至多出现两次。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

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.

对于每个测试用例，输出 $n-1$ 个整数——即在依次添加顶点 $2, 3, \ldots, n$ 后，所有可能的“多样着色”（diverse coloring）方案中，树的最小失衡值（disbalance）。

接着，输出一个长度为 $n$ 的由字符 'w' 和 'b' 组成的字符串，描述在添加完顶点 $n$ 后，使整棵树达到最小可能失衡值的一种多样着色方案：若顶点 $i$ 被染成白色，则第 $i$ 个字符为 'w'；若被染成蓝色，则为 'b'。该字符串中 'w' 与 'b' 的数量之差的绝对值必须等于上一步输出的最后一个整数。此外，每个顶点都必须至少有一个父节点或子节点，其颜色与该顶点自身颜色相反。

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

在第一个测试用例中，以下展示了所有中间树的最小可能不平衡度下的多样着色示例：