P1684 - [GESP202406 六级] 二叉树

内存限制：128 MB 时间限制：1.000 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：0 通过：0

小杨有⼀棵包含 $n$ 个节点的二叉树，且根节点的编号为 $1$。这棵二叉树任意⼀个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行 $q$ 次操作，每次小杨会选择⼀个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。

小杨想知道 $q$ 次操作全部完成之后每个节点的颜色。

第⼀行一个正整数 $n$，表示二叉树的节点数量。

第二行 $(n-1)$ 个正整数，第 $i$（$1\le i\le n-1$）个数表示编号为 $(i+1)$ 的节点的父亲节点编号，数据保证是⼀棵二叉树。

第三行一个长度为 $n$ 的 $\texttt{01}$ 串，从左到右第 $i$（$1\le i\le n$）位如果为 $\texttt{0}$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。

第四行⼀个正整数 $q$，表示操作次数。

接下来 $q$ 行每行⼀个正整数 $a_i$（$1\le a_i\le n$），表示第 $i$ 次操作选择的节点编号。

输出一行一个长度为 $n$ 的 $\texttt{01}$ 串，表示 $q$ 次操作全部完成之后每个节点的颜色。从左到右第 $i$（$1\le i\le n$）位如果为 $\texttt{0}$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。

#### 样例解释

第一次操作后，节点颜色为：$\texttt{011010}$

第二次操作后，节点颜色为：$\texttt{000000}$

第三次操作后，节点颜色为：$\texttt{010000}$

#### 数据范围

| 子任务编号 | 得分 | $n$ | $q$ | 特殊条件 |
| :--: | :--: | :--: | :--: | :--: |
| $1$ | $20$ | $\le 10^5$ | $\le 10^5$ |对于所有 $i\ge 2$，节点 $i$ 的父亲节点编号为 $i-1$
| $2$ | $40$ | $\le 1000$ | $\le 1000$ | |
| $3$ | $40$ | $\le 10^5$ | $\le 10^5$ | |

对于全部数据，保证有 $n,q\le 10^5$。

二叉树

1684: [GESP202406 六级] 二叉树

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签