在战场上,赵云指挥着一支由 n 个小队组成的军队,这些小队的组织形式类似一棵二叉树,根节点代表赵云所在的核心小队,编号为1。每个小队都持有一面军旗,军旗的颜色只有红色和蓝色两种。在战斗过程中,赵云会下达 q 次指令,每次指令会指定一个小队,该小队及以它为根的“下属”小队(在二叉树结构里即子树中的所有小队)都要将自己的军旗颜色反转(红色变蓝色,蓝色变红色)。赵云想知道执行完这 q 次指令后,每个小队军旗的最终颜色。
第一行输入一个正整数 n,表示军队中小队的数量。
第二行输入 (n - 1) 个正整数,第 i(1\leq i\leq n - 1) 个数表示编号为 (i + 1) 的小队的直属上级小队编号,这些数据保证能构成一棵二叉树。
第三行输入一个长度为 n 的字符串,字符串仅由“R”和“B”组成,从左到右第 i(1\leq i\leq n) 位如果是“R”,表示编号为 i 的小队初始军旗颜色是红色;如果是“B”,则表示初始军旗颜色是蓝色。
第四行输入一个正整数 q,代表赵云下达指令的次数。
接下来 q 行,每行一个正整数 k_{i}(1\leq k_{i}\leq n),表示第 i 次指令指定的小队编号。
输出一行长度为 n 的字符串,由“R”和“B”组成。从左到右第 i(1\leq i\leq n) 位如果是“R”,表示编号为 i 的小队执行完所有指令后的军旗颜色为红色;如果是“B”,则表示军旗颜色为蓝色 。
4 1 1 2 RBRB 2 1 2
BBBB
样例解释:
第一次指令(对编号1小队操作)执行后,各小队军旗颜色变为:BRBR。
第二次指令(对编号2小队操作)执行后,各小队军旗颜色变为:BBBB。
数据范围:
- 40\% 的数据满足 n\leq1000,q\leq1000。
- 60\% 的数据满足 n\leq10^{5},q\leq10^{5}。
时间限制 | 1 秒 |
内存限制 | 128 MB |