← 返回题单

题单练习 GESP六级真题-编程题

← 上一题下一题 →

A5295 | $[GESP202406 六级] 二叉树$

来源2024

时间限制1s

内存限制512MB

通过 / 提交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$ 的节点颜色为白色，否则为黑色。

输入输出样例

输入 #1

输出 #1

C++ 编辑器

输入

输出