题解：P10722 [GESP202406 六级] 二叉树

stripe_python · 2024-07-09 17:36:25 · 题解

给一个类似线段树的考场思路。

在每个节点维护一个当前颜色 col，一个标记 tag，表示实际颜色与 col 是否相同。

更新的时候，注意先下传标记，修改结束后再写个 dfs 全部下传一遍。复杂度 O(n)。

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

int n, fa, ls[N], rs[N], col[N], rev[N], q, a;
char x;

void pushdown(int rt) {
    if (!rev[rt]) return;
    rev[rt] ^= 1, col[rt] ^= 1;
    rev[ls[rt]] ^= 1, rev[rs[rt]] ^= 1;
}
void dfs(int rt) {
    if (!rt) return;
    pushdown(rt);
    dfs(ls[rt]), dfs(rs[rt]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cin >> n;
    for (int i = 2; i <= n; i++) {
        cin >> fa;
        (ls[fa] ? rs[fa] : ls[fa]) = i;
    }
    for (int i = 1; i <= n; i++) cin >> x, col[i] = x - '0';
    for (cin >> q; q--; ) {
        cin >> a;
        pushdown(a); 
        rev[a] ^= 1;
    }
    dfs(1);
    for (int i = 1; i <= n; i++) cout << col[i];
    return 0;
}