欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：GESP认证C++编程真题解析 | 汇总
【题目来源】
洛谷：[P10722 GESP202406 六级] 二叉树 - 洛谷
【题目描述】
小杨有一棵包含n nn个节点的二叉树，且根节点的编号为1 11。这棵二叉树任意一个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行q qq次操作，每次小杨会选择一个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。
小杨想知道q qq次操作全部完成之后每个节点的颜色。
【输入】
第一行一个正整数n nn，表示二叉树的节点数量。
第二行( n − 1 ) (n-1)(n−1)个正整数，第i ii（1 ≤ i ≤ n − 1 1\le i\le n-11≤i≤n−1）个数表示编号为( i + 1 ) (i+1)(i+1)的节点的父亲节点编号，数据保证是一棵二叉树。
第三行一个长度为n nn的01 \texttt{01}01串，从左到右第i ii（1 ≤ i ≤ n 1\le i\le n1≤i≤n）位如果为0 \texttt{0}0，表示编号为i ii的节点颜色为白色，否则为黑色。
第四行一个正整数q qq，表示操作次数。
接下来q qq行每行一个正整数a i a_iai（1 ≤ a i ≤ n 1\le a_i\le n1≤ai≤n），表示第i ii次操作选择的节点编号。
【输出】
输出一行一个长度为n nn的01 \texttt{01}01串，表示q qq次操作全部完成之后每个节点的颜色。从左到右第i ii（1 ≤ i ≤ n 1\le i\le n1≤i≤n） 位如果为0 \texttt{0}0，表示编号为i ii的节点颜色为白色，否则为黑色。
【输入样例】
6 3 1 1 3 4 100101 3 1 3 2【输出样例】
010000【算法标签】
《洛谷 P10722 二叉树》 #树形数据结构# #图遍历# #树的遍历# #GESP# #2024#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;// 树结构intn,q;// n: 节点数, q: 操作次数intfa[N];// fa[i]: 节点i的父节点编号intlc[N],rc[N];// lc[i]: 节点i的左儿子编号, rc[i]: 节点i的右儿子编号intcnt[N];// cnt[i]: 节点i被直接操作的次数string s;// s: 每个节点的字符（'0'或'1'）// 深度优先搜索，将父节点的操作次数传递到子节点// x: 当前节点// f: 父节点的累计操作次数voiddfs(intx,intf){// 当前节点的累计操作次数 = 直接操作次数 + 父节点的累计操作次数cnt[x]+=cnt[f];// 递归处理左子树if(lc[x]){dfs(lc[x],x);}// 递归处理右子树if(rc[x]){dfs(rc[x],x);}}intmain(){// 输入节点数cin>>n;// 构建树结构for(inti=2;i<=n;i++)// 节点1是根节点{intx;cin>>x;// 输入节点i的父节点fa[i]=x;// 记录父节点关系// 将当前节点i作为父节点x的子节点// 先尝试作为左儿子，如果左儿子已有，则作为右儿子if(!lc[x]){lc[x]=i;// 作为左儿子}if(lc[x]!=i&&!rc[x]){rc[x]=i;// 作为右儿子}}// 输入每个节点的字符cin>>s;// 输入操作次数cin>>q;// 在字符串前加空格，使索引从1开始s=' '+s;// 处理每个操作while(q--){intx;cin>>x;// 对节点x进行操作cnt[x]++;// 记录节点x被操作的次数}// 从根节点开始DFS，传递操作次数dfs(1,0);// 根节点1的父节点累计操作为0// 输出最终字符串for(inti=1;i<=n;i++){// 如果节点i的总操作次数是奇数，字符取反if(cnt[i]&1)// cnt[i]是奇数{// 奇数次操作：'0'变'1'，'1'变'0'cout<<(s[i]=='0');// 如果s[i]是'0'，输出1；否则输出0}else// cnt[i]是偶数{// 偶数次操作：字符不变cout<<s[i];}}cout<<endl;return0;}【运行结果】
6 3 1 1 3 4 100101 3 1 3 2 010000
