q 次"翻转某结点子树内所有颜色"的操作后,求最终颜色。
有一棵 n 个结点的二叉树(根为 1),每个结点是黑色(1)或白色(0)。进行 q 次操作,每次选一个结点 a,把以 a 为根的子树内所有结点颜色反转。求 q 次操作后每个结点的颜色。
子树操作翻转奇偶祖先累加O(n+q)
| 项目 | 说明 |
|---|---|
| 输入 | n;n−1 个父结点;01 串;q;q 个被选结点 |
| 输出 | 一行长度 n 的 01 串 |
| 数据范围 | n, q ≤ 10⁵ |
| 操作 | 翻转以 a 为根的子树内所有颜色 |
| 便利条件 | 父结点编号一定小于子结点编号 |
O(nq) = 10¹⁰,必然超时cnt[a] 为结点 a 被选中的次数。结点 v 的翻转次数 = Σ cnt[u](u 遍历 v 及其所有祖先)flip[v] = flip[parent(v)] + cnt[v];由于父结点编号更小,按编号 1→n 顺序递推即可先理清树的结构(结点 2~6 的父结点依次是 3、1、1、3、4)。
| 结点 | 父结点 |
|---|---|
| 2 | 3 |
| 3 | 1 |
| 4 | 1 |
| 5 | 3 |
| 6 | 4 |
树形:1 → {3, 4};3 → {2, 5};4 → {6}
初始颜色(1 起):1=1、2=0、3=0、4=1、5=0、6=1。
操作序列:1、3、2
cnt[1] = 1(被选 1 次)
cnt[3] = 1
cnt[2] = 1
其他 cnt = 0
cnt = {1:1, 2:1, 3:1}
flip[1] = cnt[1] = 1
flip[2] = flip[3] + cnt[2];先算 flip[3]
flip[3] = flip[1] + cnt[3] = 1 + 1 = 2
所以 flip[2] = 2 + 1 = 3
flip[4] = flip[1] + cnt[4] = 1 + 0 = 1
flip[5] = flip[3] + cnt[5] = 2 + 0 = 2
flip[6] = flip[4] + cnt[6] = 1 + 0 = 1
flip = {1, 3, 2, 1, 2, 1}
结点 1:1 XOR (1%2=1) = 0
结点 2:0 XOR (3%2=1) = 1
结点 3:0 XOR (2%2=0) = 0
结点 4:1 XOR (1%2=1) = 0
结点 5:0 XOR (2%2=0) = 0
结点 6:1 XOR (1%2=1) = 0
✅ 输出 "010000"
| 结点 | 初始色 | cnt | flip | flip 奇偶 | 最终色 |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 奇 | 0 |
| 2 | 0 | 1 | 3 | 奇 | 1 |
| 3 | 0 | 1 | 2 | 偶 | 0 |
| 4 | 1 | 0 | 1 | 奇 | 0 |
| 5 | 0 | 0 | 2 | 偶 | 0 |
| 6 | 1 | 0 | 1 | 奇 | 0 |
输出 "010000" ✓
flip[2] = 3:结点 2 被翻转了 3 次——因为它的祖先里有结点 1(被选 1 次)、结点 3(被选 1 次),再加上自己被选 1 次,共 3 次。flip[父] + cnt[自己]。为了确认结论正确,我们按题目描述实际模拟一次。
| 步骤 | 操作 | 操作后颜色串 |
|---|---|---|
| 初始 | — | 100101 |
| 第 1 次 | 翻转以 1 为根的子树(整棵树) | 011010 |
| 第 2 次 | 翻转以 3 为根的子树(结点 3、2、5) | 000000 |
| 第 3 次 | 翻转以 2 为根的子树(只有结点 2) | 010000 |
实际模拟结果 "010000" ✓ 与算法结论一致
O(nq);而计数法只需 O(n + q)——这正是"观察出可累加的不变量"带来的巨大优化。统计每个结点被选次数,从根往下累加得到翻转次数,取奇偶
cnt[a]++(读操作时统计);flip[v] = flip[par[v]] + cnt[v](按编号递增递推)。利用了"父结点编号更小"这个条件,所以完全不需要建图、不需要 DFS。每次操作用 DFS 遍历子树并翻转颜色
| 方案 | 复杂度 | 可行性 |
|---|---|---|
| 祖先计数 | O(n + q) | ✅ 稳过 |
| 暴力翻转 | O(nq) | ❌ 超时 |
第一行输入 n,第二行输入父结点,第三行输入颜色串,第四行输入操作数与操作。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int par[100005], cnt[100005], flip[100005]; char s[100005]; int main() { int n; scanf("%d", &n); for (int i = 2; i <= n; i++) scanf("%d", &par[i]); // 题目保证 par[i] < i scanf("%s", s + 1); // 1-based 颜色串 int q; scanf("%d", &q); for (int i = 0; i < q; i++) { int a; scanf("%d", &a); cnt[a]++; // 只统计次数,不做翻转 } flip[1] = cnt[1]; for (int v = 2; v <= n; v++) { flip[v] = flip[par[v]] + cnt[v]; // 祖先累加 } for (int v = 1; v <= n; v++) { int init = s[v] - '0'; int fin = init ^ (flip[v] & 1); // 奇数次翻转才变色 putchar('0' + fin); } putchar('\n'); return 0; }
| 代码 | 作用 | 为什么这样写 |
|---|---|---|
cnt[a]++ | 统计选次 | 不真的翻转子树 |
flip[1] = cnt[1] | 根的翻转次数 | 根的祖先只有自己 |
flip[v] = flip[par[v]] + cnt[v] | 递推 | 父结点编号更小,所以按顺序递推即可 |
init ^ (flip[v] & 1) | 最终颜色 | 奇数次翻转才变 |
O(nq) 超时);② 递推时写成 cnt[par[v]] + cnt[v](只算了父和己,漏了更远的祖先);③ 忘记"自己也要算"(漏 + cnt[v]);④ 用 % 判断奇偶而不用位运算(都对,但位运算更快)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
6 | 010000 | 题面样例 |
3 | 111 | 翻转以根为根的整棵树,三个结点全变色 |
3 | 000 | 同一结点选两次,等于没翻 |
2 | 11 | 翻转整棵树(根为 1,子树含结点 2) |
2 | 00 | 只翻结点 2 的子树:结点 2 由 1 变 0 |
flip[par] 而不是 cnt[par]。+ cnt[v]。cnt:O(q)flip:O(n)需要 par、cnt、flip 三个长度 n+1 的数组。
✅ 约 20 万次操作,瞬间完成。相比暴力翻转的 10¹⁰,快了五个数量级。
// 核心观察 // 子树整体操作 <=> 每个后代被操作一次 // 所以只需统计"每个点被选中的次数",再从根往下累加 // 一般树(父结点编号不一定小于子结点)的做法 // 思路一样,只是累加要用拓扑序(BFS/DFS): vector<int> order; // BFS 顺序 for (int u : order) // 按拓扑序从根往下 for (int v : children[u]) flip[v] = flip[u] + cnt[v]; // 类似"区间整体操作"的差分技巧 // 一维数组区间加 -> 差分数组,最后做前缀和 // 树上的子树操作 -> 本题这种"祖先累加" // 二者本质相同:把"范围操作"转成"端点标记 + 一次扫描" // 常见变体 // - 子树加、子树赋值(配合欧拉序转成区间) // - 路径操作(配合树上差分) // - 多次整体反转(本题)
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 子树操作转计数 | 祖先累加 | 所有"整棵子树统一操作"的题 |
| 翻转只看奇偶 | 两次抵消 | 只有两种状态的反复操作 |
| 差分思想 | 端点标记 + 一次扫描 | 区间/子树批量操作 |
cnt[a]++,最后自底向上累加到根即可。注意方向变了:子树操作是"自顶向下累加",路径操作是"自底向上累加"。)