310093: CF1781G. Diverse Coloring
Memory Limit：512 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Diverse Coloring
题意翻译
对于一颗二叉树，一个合法的染色方案定义为将每个点染成白色或蓝色，所有蓝色点有白色点邻居，白色点有蓝色点邻居。一种合法染色方案的平衡值定义为蓝色点与白色点数量差的绝对值。 有一颗给定的 $n$ 个点的二叉树，第 $i$ 个点的父亲是 $p_i(p_i < i)$，请对于 $\forall 1 < i \leqslant n$，求出只保留树上编号在 $[1, i]$ 的点时，所有合法染色方案的平衡值最小值。同时对整棵树求出一个合法染色方案取到这个最小值。 共 $T$ 组测试数据，$T \leqslant 10^4, n > 1, \sum n \leqslant 2 \cdot 10^5$。题目描述
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.输入输出格式
输入格式
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 $ .
输出格式
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.
输入输出样例
输入样例 #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说明
In the first test case, examples of diverse colorings with the smallest possible disbalances for all intermediate trees are illustrated below: Input
题意翻译
对于一颗二叉树，一个合法的染色方案定义为将每个点染成白色或蓝色，所有蓝色点有白色点邻居，白色点有蓝色点邻居。一种合法染色方案的平衡值定义为蓝色点与白色点数量差的绝对值。 有一颗给定的 $n$ 个点的二叉树，第 $i$ 个点的父亲是 $p_i(p_i < i)$，请对于 $\forall 1 < i \leqslant n$，求出只保留树上编号在 $[1, i]$ 的点时，所有合法染色方案的平衡值最小值。同时对整棵树求出一个合法染色方案取到这个最小值。 共 $T$ 组测试数据，$T \leqslant 10^4, n > 1, \sum n \leqslant 2 \cdot 10^5$。Output
**题意翻译**
题目描述了一个二叉树的染色问题。在这个问题中，我们需要对二叉树中的每个节点进行染色，可以是白色或蓝色。一个合法的染色方案要求树中任意节点的邻居（父节点或子节点）颜色与自己不同。染色方案的平衡值定义为蓝色节点数与白色节点数差的绝对值。
给定一个有 $ n $ 个节点的二叉树，每个节点的父节点由 $ p_i $ 表示（$ p_i < i $），需要计算在只保留树上编号在 $ [1, i] $ 的点时，所有合法染色方案的平衡值的最小值。同时，对于整棵树，需要找出一个合法染色方案，使得平衡值达到这个最小值。
共有 $ T $ 组测试数据，满足 $ T \leqslant 10^4, n > 1, \sum n \leqslant 2 \cdot 10^5 $。
**题目描述**
在这个问题中，我们在有根二叉树上进行操作。一个有根二叉树有一个固定的根节点，并且每个节点最多有两个子节点。
我们对树上的每个节点分配白色或蓝色，并称这个分配为树的染色。如果一个染色方案使得每个节点都有一个邻居（父节点或子节点）的颜色与该节点相反，我们称这个染色方案为多样化的。可以证明，任何至少有两个节点的树都允许一个多样化的染色。
我们定义一个染色方案的失衡值为白色节点数与蓝色节点数差的绝对值。
现在到问题本身。最初，树由一个编号为 $ 1 $ 的节点组成，它是根节点。然后，对于每个 $ i $ 从 $ 2 $ 到 $ n $，一个新的编号为 $ 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'，如果被染成蓝色，则为 '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
```
在第一个测试案例中，对于所有中间树的具有最小可能失衡值的多样化染色方案的例子如下所示：
**题意翻译** 题目描述了一个二叉树的染色问题。在这个问题中，我们需要对二叉树中的每个节点进行染色，可以是白色或蓝色。一个合法的染色方案要求树中任意节点的邻居（父节点或子节点）颜色与自己不同。染色方案的平衡值定义为蓝色节点数与白色节点数差的绝对值。 给定一个有 $ n $ 个节点的二叉树，每个节点的父节点由 $ p_i $ 表示（$ p_i < i $），需要计算在只保留树上编号在 $ [1, i] $ 的点时，所有合法染色方案的平衡值的最小值。同时，对于整棵树，需要找出一个合法染色方案，使得平衡值达到这个最小值。 共有 $ T $ 组测试数据，满足 $ T \leqslant 10^4, n > 1, \sum n \leqslant 2 \cdot 10^5 $。 **题目描述** 在这个问题中，我们在有根二叉树上进行操作。一个有根二叉树有一个固定的根节点，并且每个节点最多有两个子节点。 我们对树上的每个节点分配白色或蓝色，并称这个分配为树的染色。如果一个染色方案使得每个节点都有一个邻居（父节点或子节点）的颜色与该节点相反，我们称这个染色方案为多样化的。可以证明，任何至少有两个节点的树都允许一个多样化的染色。 我们定义一个染色方案的失衡值为白色节点数与蓝色节点数差的绝对值。 现在到问题本身。最初，树由一个编号为 $ 1 $ 的节点组成，它是根节点。然后，对于每个 $ i $ 从 $ 2 $ 到 $ n $，一个新的编号为 $ 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'，如果被染成蓝色，则为 '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 ``` 在第一个测试案例中，对于所有中间树的具有最小可能失衡值的多样化染色方案的例子如下所示： 
题目描述了一个二叉树的染色问题。在这个问题中，我们需要对二叉树中的每个节点进行染色，可以是白色或蓝色。一个合法的染色方案要求树中任意节点的邻居（父节点或子节点）颜色与自己不同。染色方案的平衡值定义为蓝色节点数与白色节点数差的绝对值。
给定一个有 $ n $ 个节点的二叉树，每个节点的父节点由 $ p_i $ 表示（$ p_i < i $），需要计算在只保留树上编号在 $ [1, i] $ 的点时，所有合法染色方案的平衡值的最小值。同时，对于整棵树，需要找出一个合法染色方案，使得平衡值达到这个最小值。
共有 $ T $ 组测试数据，满足 $ T \leqslant 10^4, n > 1, \sum n \leqslant 2 \cdot 10^5 $。
**题目描述**
在这个问题中，我们在有根二叉树上进行操作。一个有根二叉树有一个固定的根节点，并且每个节点最多有两个子节点。
我们对树上的每个节点分配白色或蓝色，并称这个分配为树的染色。如果一个染色方案使得每个节点都有一个邻居（父节点或子节点）的颜色与该节点相反，我们称这个染色方案为多样化的。可以证明，任何至少有两个节点的树都允许一个多样化的染色。
我们定义一个染色方案的失衡值为白色节点数与蓝色节点数差的绝对值。
现在到问题本身。最初，树由一个编号为 $ 1 $ 的节点组成，它是根节点。然后，对于每个 $ i $ 从 $ 2 $ 到 $ n $，一个新的编号为 $ 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'，如果被染成蓝色，则为 '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
```
在第一个测试案例中，对于所有中间树的具有最小可能失衡值的多样化染色方案的例子如下所示：
**题意翻译** 题目描述了一个二叉树的染色问题。在这个问题中，我们需要对二叉树中的每个节点进行染色，可以是白色或蓝色。一个合法的染色方案要求树中任意节点的邻居（父节点或子节点）颜色与自己不同。染色方案的平衡值定义为蓝色节点数与白色节点数差的绝对值。 给定一个有 $ n $ 个节点的二叉树，每个节点的父节点由 $ p_i $ 表示（$ p_i < i $），需要计算在只保留树上编号在 $ [1, i] $ 的点时，所有合法染色方案的平衡值的最小值。同时，对于整棵树，需要找出一个合法染色方案，使得平衡值达到这个最小值。 共有 $ T $ 组测试数据，满足 $ T \leqslant 10^4, n > 1, \sum n \leqslant 2 \cdot 10^5 $。 **题目描述** 在这个问题中，我们在有根二叉树上进行操作。一个有根二叉树有一个固定的根节点，并且每个节点最多有两个子节点。 我们对树上的每个节点分配白色或蓝色，并称这个分配为树的染色。如果一个染色方案使得每个节点都有一个邻居（父节点或子节点）的颜色与该节点相反，我们称这个染色方案为多样化的。可以证明，任何至少有两个节点的树都允许一个多样化的染色。 我们定义一个染色方案的失衡值为白色节点数与蓝色节点数差的绝对值。 现在到问题本身。最初，树由一个编号为 $ 1 $ 的节点组成，它是根节点。然后，对于每个 $ i $ 从 $ 2 $ 到 $ n $，一个新的编号为 $ 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'，如果被染成蓝色，则为 '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 ``` 在第一个测试案例中，对于所有中间树的具有最小可能失衡值的多样化染色方案的例子如下所示： 