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

①比较朴素的思路为建树,每次操作时执行DFS,将操作的结果处理,最终输出每个节点颜色,极端情况下每次操作遍历整棵树的话,复杂度O(nq),只能解决40%的数据。
②考虑到程序只要最终结果,因此中间结果没必要完全求得,取反操作的周期为2,具有奇偶性,因此每次操作X时,将X的位置打个标记,表示其将影响X下方的每个节点翻转一次,当所有操作标记完,执行DFS,从root=1出发,统计到达每个节点X时的标记的数量cnt,如果cnt为奇数,则改点颜色取反,否则保持原来颜色。这样只需要O(n+q)的复杂度。