← 返回题目列表

Codeforces · 1781/G

G. 色彩多样

中文机器翻译题面 查看原题

在这个问题中,我们将使用有根二叉树。如果一棵树具有固定的根并且每个顶点最多有两个子节点,则该树称为有根二叉树。

让我们为树的每个顶点指定一种颜色(白色或蓝色),并将此指定称为树的着色。如果每个顶点都有一个邻居(父顶点或子顶点)着色为与该顶点相反的颜色,那么我们将着色称为多样化。可以证明,任何至少有两个顶点的树都允许多种颜色。

让我们将着色的不平衡定义为白色顶点数与蓝色顶点数之差的绝对值。

现在解决问题。最初,树由一个顶点组成,编号为 $$$1$$$ 是其根。然后,对于从 $$$2$$$ 到 $$$n$$$ 的每个 $$$i$$$,树中会出现一个新顶点 $$$i$$$,并且它成为顶点 $$$p_i$$$ 的子节点。保证每一步之后树都将保持为以顶点 $$$1$$$ 为根的二叉树,即每个顶点最多有两个子节点。

添加每个新顶点后,打印当前树的所有可能的不同着色的不平衡的最小值。此外,在添加带有数字 $$$n$$$ 的最后一个顶点后,还以尽可能最小的不平衡打印多种颜色。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 为白色,则第 $$$i$$$ 个字符必须等于 'w',如果顶点 $$$i$$$ 为蓝色,则必须等于 'b'。 “w”和“b”字符数之差的绝对值必须等于最后打印的整数。每个顶点必须有一个父级或子级,其颜色与该顶点的颜色相反。

示例

输入 #1

2
7
1 2 2 1 5 5
8
1 2 3 4 5 6 7

输出 #1

0
1
2
1
0
1
wbwwwbb
0
1
0
1
0
1
0
wbwbwbwb

注意

在第一个测试用例中,所有中间树具有最小可能不平衡的不同着色示例如下所示: