《P10722 [GESP202406 六级] 二叉树》

题目背景对应的选择、判断题试题 - GESP 202406 C 六级 - 洛谷有题题目描述小杨有一棵包含 n 个节点的二叉树且根节点的编号为 1。这棵二叉树任意一个节点要么是白色要么是黑色。之后小杨会对这棵二叉树进行 q 次操作每次小杨会选择一个节点将以这个节点为根的子树内所有节点的颜色反转即黑色变成白色白色变成黑色。小杨想知道 q 次操作全部完成之后每个节点的颜色。输入格式第一行一个正整数 n表示二叉树的节点数量。第二行 (n−1) 个正整数第 i1≤i≤n−1个数表示编号为 (i1) 的节点的父亲节点编号数据保证是一棵二叉树。第三行一个长度为 n 的 01 串从左到右第 i1≤i≤n位如果为 0表示编号为 i 的节点颜色为白色否则为黑色。第四行一个正整数 q表示操作次数。接下来 q 行每行一个正整数 ai​1≤ai​≤n表示第 i 次操作选择的节点编号。输出格式输出一行一个长度为 n 的 01 串表示 q 次操作全部完成之后每个节点的颜色。从左到右第 i1≤i≤n 位如果为 0表示编号为 i 的节点颜色为白色否则为黑色。输入输出样例输入 #1复制6 3 1 1 3 4 100101 3 1 3 2输出 #1复制010000说明/提示样例解释第一次操作后节点颜色为011010第二次操作后节点颜色为000000第三次操作后节点颜色为010000数据范围子任务编号得分nq特殊条件120≤105≤105对于所有 i≥2节点 i 的父亲节点编号为 i−1240≤1000≤1000340≤105≤105对于全部数据保证有 n,q≤105。代码实现#include bits/stdc.h using namespace std; const int N100005; int n,q,tag[N]; vectorint 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 i2;in;i){int f;scanf(%d,f);e[f].push_back(i);} scanf(%s,col1); scanf(%d,q); while(q--){int a;scanf(%d,a);tag[a]^1;} dfs(1,0); for(int i1;in;i) putchar(ans[i]); return 0; }