CF1781G Diverse Coloring

在本题中，我们将处理有根二叉树。若一棵树有一个固定的根，并且每个结点最多有两个子结点，则称其为有根二叉树。 我们为树中的每个结点分配一种颜色——白色或蓝色，这种分配称为树的着色。如果树的每个结点都至少有一个邻居（父结点或子结点）与其颜色相反，则称该着色为“多样着色”。可以证明，任何至少有两个结点的树都存在多样着色。 我们定义一种着色的“失衡度”为白色结点数与蓝色结点数之差的绝对值。 现在问题如下。最初，树只有一个编号为 $1$ 的结点，作为根。然后，对于每个 $i$ 从 $2$ 到 $n$，新结点 $i$ 出现在树中，并成为结点 $p_i$ 的子结点。保证每一步后，树仍然是以结点 $1$ 为根的二叉树，即每个结点最多有两个子结点。 每次添加新结点后，输出当前树所有可能的多样着色中最小的失衡度。并且，在添加最后一个编号为 $n$ 的结点后，还要输出一种具有最小失衡度的多样着色方案。具体地，输出一个长度为 $n$ 的字符串，字符为 'w' 表示该结点为白色，'b' 表示蓝色。要求每个结点都至少有一个父结点或子结点与其颜色相反。

每个测试包含多组数据。第一行包含一个整数 $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$。

对于每个测试用例，输出 $n-1$ 个整数，分别表示每次添加结点 $2, 3, \ldots, n$ 后，所有可能的多样着色中最小的失衡度。 然后输出一个长度为 $n$ 的字符串，由 'w' 和 'b' 组成，表示在添加结点 $n$ 后，具有最小失衡度的多样着色方案。第 $i$ 个字符为 'w' 表示结点 $i$ 着白色，'b' 表示蓝色。'w' 和 'b' 的数量之差的绝对值应等于最后输出的整数。每个结点都必须有一个父结点或子结点与其颜色相反。

在第一个测试用例中，所有中间树的最小失衡度的多样着色示例如下图所示：  由 ChatGPT 4.1 翻译