题目背景
对应的选择、判断题：试题 - GESP 202406 C++ 六级 - 洛谷有题
题目描述
小杨有一棵包含 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 的节点颜色为白色，否则为黑色。
输入输出样例
输入 #1复制
6 3 1 1 3 4 100101 3 1 3 2
输出 #1复制
010000
说明/提示
样例解释
第一次操作后，节点颜色为：011010
第二次操作后，节点颜色为：000000
第三次操作后，节点颜色为：010000
数据范围
| 子任务编号 | 得分 | n | q | 特殊条件 |
|---|---|---|---|---|
| 1 | 20 | ≤105 | ≤105 | 对于所有 i≥2，节点 i 的父亲节点编号为 i−1 |
| 2 | 40 | ≤1000 | ≤1000 | |
| 3 | 40 | ≤105 | ≤105 |
对于全部数据，保证有 n,q≤105。
代码实现：
#include <bits/stdc++.h> using namespace std; const int N=100005; int n,q,tag[N]; vector<int> e[N]; char col[N], ans[N]; void dfs(int u, int cur){ cur ^= tag[u]; ans[u] = ((col[u]-'0') ^ cur) + '0'; for(int v:e[u]) dfs(v, cur); } int main(){ scanf("%d",&n); for(int i=2;i<=n;i++){int f;scanf("%d",&f);e[f].push_back(i);} scanf("%s",col+1); scanf("%d",&q); while(q--){int a;scanf("%d",&a);tag[a]^=1;} dfs(1,0); for(int i=1;i<=n;i++) putchar(ans[i]); return 0; }
