g6-02680. GESP-6级-2024-06-二叉树

题目描述

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

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

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

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

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

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

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

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

输入

输出

第一次操作后，节点颜色为： $011010$

第二次操作后，节点颜色为： $000000$

第三次操作后，节点颜色为： $010000$

子任务编号	得分	$n$	$q$	特殊条件
$1$	$20$	$\leq 1 0^{5}$	$\leq 1 0^{5}$	对于所有 $i \geq 2$ ，节点 $i$ 的父亲节点编号为 $i - 1$
$2$	$40$	$\leq 1000$	$\leq 1000$
$3$	$40$	$\leq 1 0^{5}$	$\leq 1 0^{5}$

对于全部数据，保证有 $n, q \leq 1 0^{5}$ 。

来源：洛谷 P10722（CCF GESP 六级上机题）