G6008 [GESP202406 六级] 二叉树 题解

知识点：树遍历、异或、标记传递。

解题思路

每个操作节点先把本地flip异或1，再从根向下遍历，将父节点累计翻转标记传给孩子，并修改当前颜色。

为什么正确

节点受到的影响等于所有祖先操作次数的奇偶性，异或累积恰表达这一关系，多次翻转自动抵消。

易错点

相同节点操作两次无效果；必须先更新当前累计标记，再传给后代。

复杂度

时间O(n+q)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<int>>ch(n+1);
    for(int i=2;i<=n;i++) {
        int p;
        cin>>p;
        ch[p].push_back(i);
    }
    string s;
    cin>>s;
    vector<int>flip(n+1);
    int q;
    cin>>q;
    while(q--) {
        int x;
        cin>>x;
        flip[x]^=1;
    }
    vector<int>order= {
        1
    }
    ;
    for(int x:order) {
    }
    for(int k=0;k<(int)order.size();k++) {
        int x=order[k];
        s[x-1]=char('0'+((s[x-1]-'0')^flip[x]));
        for(int y:ch[x]) {
            flip[y]^=flip[x];
            order.push_back(y);
        }
    }
    cout<<s;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。