自动搬运

查看原文

来自洛谷，原作者为

	stripe_python 蛰伏的痛，终将化作闪电撕裂长空！|| 最后在线时间：2025年8月24日20时56分

搬运于2025-08-24 23:00:38，当前版本为作者最后更新于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;
}