CCF-GESP计算机学会等级考试2024年6月六级C++T2二叉树

解析：

详见代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int q;
string s;
int p[100005];//p[i]表示i的父节点
int a[100005];//对第i个节点的操作次数
int b[100005];//第i个节点变化的总次数
int dfs(int x){
    if (b[x]>0) return b[x];//如果已计算，直接返回结果
    b[x]=a[x]+dfs(p[x]);//当前节点的操作次数加上父节点的总操作次数
    return b[x];
}
int main() {
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>p[i];
    }
    cin>>s;
    cin>>q;
    for(int i=1;i<=q;i++){
        int op;
        cin>>op;
        a[op]++;
    }
    b[1]=a[1]+2;//多两次操作不影响结果，可以保证b数组都大于0
    for(int i=1;i<=n;i++){
        if(b[i]==0){//如果没计算
            dfs(i);//递归计算
        }
    }
    for(int i=0;i<n;i++){//枚举字符串的每一位
        bool x=s[i]-'0';//转换成布尔值
        if (b[i+1]%2==0){//偶数次
            cout<<x;//直接输出
        }else{//奇数次
            cout<<!x;//输出相反
        }
    }
    return 0;
}