A1779 [GESP-6.2406.T2] 二叉树

#include <bits/stdc++.h>
using namespace std;

// [GESP-6.2406.T2] 二叉树：子树颜色反转。
//
// 反转两次等于没反转，所以只要知道每个节点被翻转了奇数次还是偶数次。
// 对节点 u，被翻转的次数 = 它自己身上发生的操作次数 + 它所有祖先身上的操作次数。
// 于是先统计 cnt[u]（在 u 上操作的次数的奇偶），再从根往下做一次遍历：
//     flip[u] = flip[parent[u]] xor cnt[u]
// 最后把初始颜色和 flip[u] 异或即可。
//
// 注意父亲编号不一定比儿子小（样例里 parent[2] = 3），所以必须真的从根出发遍历，
// 不能直接按编号从小到大递推。

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;

    int q;
    cin >> q;
    vector<int> cnt(n + 1, 0);
    for (int i = 0; i < q; i++) {
        int a;
        cin >> a;
        cnt[a] ^= 1;
    }

    // 从根 1 出发做一次广度优先遍历，累加翻转次数的奇偶
    vector<int> par(n + 1, 0), flip(n + 1, 0), order;
    order.reserve(n);
    order.push_back(1);
    for (size_t i = 0; i < order.size(); i++) {
        int u = order[i];
        flip[u] = flip[par[u]] ^ cnt[u];
        for (int v : ch[u]) {
            par[v] = u;
            order.push_back(v);
        }
    }

    string ans(n, '0');
    for (int i = 1; i <= n; i++) {
        char c = s[i - 1];
        if (flip[i]) c = (c == '0' ? '1' : '0');
        ans[i - 1] = c;
    }

    cout << ans << "\n";
    return 0;
}