二叉树 6级2 2024.6

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

3.2.1题面描述
小杨有一棵包含n个节点的二叉树,且根节点的编号为1。这棵二叉树任意一个节点要么是白色,要么是黑色。之后小杨会对这棵二叉树进行q次操作,每次小杨会选择一个节点,将以这个节点为根的子树内所有节点的颜色反转,即黑色变成白色,白色变成黑色。
小杨想知道q次操作全部完成之后每个节点的颜色。
3.2.2输入格式
第一行一个正整数n,表示二叉树的节点数量。
第二行n-1个正整数,第i (1≤i≤n-1)个数表示编号为i + 1的节点的父亲节点编号,数据保证是一棵二叉树。
第三行一个长度为n的01串,从左到右第i (1≤i≤n)位如果为0,表示编号为i的节点颜色为白色,否则为黑色。
第四行一个正整数q,表示操作次数。
接下来q行每行一个正整数a_i (1≤ai≤n),表示第i次操作选择的节点编号。
3.2.3输出格式
输出一行一个长度为n的01串,表示q次操作全部完成之后每个节点的颜色。从左到右第i (1≤i≤n)位如果为0,表示编号为i的节点颜色为白色,否则为黑色。
3.2.4 样例1
输入:
6
3 1 1 3 4
100101
3
1
3
2
输出:
010000

3.2.5样例解释
第一次操作后,节点颜色为: 011010
第二次操作后,节点颜色为: 000000
第三次操作后,节点颜色为: 010000

3.2.6 数据范围
对于全部数据,保证有1≤n,q≤10^5。

GESP6级 考前练习

未参加
状态
已结束
规则
ACM/ICPC
题目
10
开始于
2024-08-22 12:00
结束于
2024-09-08 04:00
持续时间
400.0 小时
主持人
参赛人数
9