1 solutions

  • 0
    @ 2025-11-27 11:59:02

    C++ :

    #include <bits/stdc++.h>
    using namespace std;
    const int MAX_N = 1e5 + 9;
    
    int n , q , f[MAX_N] , x , num[MAX_N] , sum;
    string color;
    vector<int>G[MAX_N];
    
    void dfs(int x)
    {
        if(num[x])
            sum++;
        if(f[x] == 0)
            return;
        dfs(f[x]);
    }
    
    void dfs(int x , bool check)
    {
        
        if(check && num[x])   //check为父结点带来的影响  num[x]为本身是否需要操作
            check = false;
        else if(!check && num[x] || check && !num[x])
            check = true;
        
        if(check)
        {
            if(color[x] == '1')
                color[x] = '0';
            else
                color[x] = '1';
        }
    
        for(auto it : G[x])
            dfs(it , check);
    }
    
    int main()
    {
        cin >> n; //二叉树的结点个数
        for(int i = 2; i <= n; i++)
        {
            cin >> f[i];  //f[i]:结点i的父亲结点的编号
            G[f[i]].push_back(i);  //儿子存储法
        }
        
        cin >> color;
        color = ' ' + color;  //color[i]:编号为i的结点的颜色,color[i]=1为黑色 color[i]=0为白色
    
        cin >> q;
    
        while(q--)  //q次询问
        {
            cin >> x;  //选择编号为x的结点
            num[x] = (num[x] + 1) % 2;  //记录根结点为x的子树操作的次数
        }
    
        dfs(1 , false);
    
        for(int i = 1; i <= n; i++)
            cout << color[i];
        return 0;
    }
    
    
    • 1

    Information

    ID
    115
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By