二叉树

描述

小杨有⼀棵包含 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≤105。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct nod{
    char date;
    int fa,lc,rc,num;
}a[N];
int n,k,T,m,dp[N];
void fun(int x){
    if(x==0) return ;
    dp[x]=dp[a[x].fa]+a[x].num;
    fun(a[x].lc);
    fun(a[x].rc);
}
int main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        cin>>k;
        a[i].fa=k;
        if(a[k].lc==0) a[k].lc=i;
        else a[k].rc=i;       
    }
    for(int i=1;i<=n;i++){
        cin>>a[i].date;
    }
    cin>>T;
    while(T--){
        cin>>m;
        a[m].num++;
    }
    fun(1);
    for(int i=1;i<=n;i++){
        if(dp[i]%2==0) cout<<a[i].date;
        else cout<<1-(a[i].date-'0');
    }
}