{"problem":{"name":"[GESP202406 六级] 二叉树","description":{"content":"小杨有一棵包含 $n$ 个节点的二叉树，且根节点的编号为 $1$。这棵二叉树任意一个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行 $q$ 次操作，每次小杨会选择一个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。 小杨想知道 $q$ 次操作全部完成之后每个节点的颜色。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10722"},"statements":[{"statement_type":"Markdown","content":"小杨有一棵包含 $n$ 个节点的二叉树，且根节点的编号为 $1$。这棵二叉树任意一个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行 $q$ 次操作，每次小杨会选择一个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。\n\n小杨想知道 $q$ 次操作全部完成之后每个节点的颜色。\n\n## Input\n\n第一行一个正整数 $n$，表示二叉树的节点数量。\n\n第二行 $(n-1)$ 个正整数，第 $i$（$1\\le i\\le n-1$）个数表示编号为 $(i+1)$ 的节点的父亲节点编号，数据保证是一棵二叉树。\n\n第三行一个长度为 $n$ 的 $\\texttt{01}$ 串，从左到右第 $i$（$1\\le i\\le n$）位如果为 $\\texttt{0}$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。\n\n第四行一个正整数 $q$，表示操作次数。\n\n接下来 $q$ 行每行一个正整数 $a_i$（$1\\le a_i\\le n$），表示第 $i$ 次操作选择的节点编号。\n\n## Output\n\n输出一行一个长度为 $n$ 的 $\\texttt{01}$ 串，表示 $q$ 次操作全部完成之后每个节点的颜色。从左到右第 $i$（$1\\le i\\le n$） 位如果为 $\\texttt{0}$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。\n\n[samples]\n\n## Background\n\n对应的选择、判断题：<https://ti.luogu.com.cn/problemset/1154>\n\n## Note\n\n#### 样例解释\n\n第一次操作后，节点颜色为：$\\texttt{011010}$\n\n第二次操作后，节点颜色为：$\\texttt{000000}$\n\n第三次操作后，节点颜色为：$\\texttt{010000}$\n\n#### 数据范围\n\n| 子任务编号 | 得分 | $n$ | $q$ | 特殊条件 |\n| :--: | :--: | :--: | :--: | :--: |\n| $1$ |  $20$ | $\\le 10^5$ | $\\le 10^5$ |对于所有 $i\\ge 2$，节点 $i$ 的父亲节点编号为 $i-1$\n| $2$ |  $40$ | $\\le 1000$ | $\\le 1000$ | |\n| $3$ | $40$ | $\\le 10^5$ | $\\le 10^5$ | |\n\n对于全部数据，保证有 $n,q\\le 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10722","tags":["树形数据结构","2024","图遍历","树的遍历","GESP"],"sample_group":[["6\n3 1 1 3 4\n100101\n3\n1\n3\n2","010000"]],"created_at":"2026-03-03 11:09:25"}}