GESP 题解库 / 6 级题解 / [GESP202406 六级] 二叉树 · 第 15 / 27 题
GESP202406 六级 · P10722 · 中等

二叉树

q 次"翻转某结点子树内所有颜色"的操作后,求最终颜色。

📊
n, q ≤ 10⁵
规模
🔢
int
数值类型
⚡
O(n + q)
时间复杂度
🎯
翻转次数奇偶 + 祖先累加
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

有一棵 n 个结点的二叉树(根为 1),每个结点是黑色(1)或白色(0)。进行 q 次操作,每次选一个结点 a,把以 a 为根的子树内所有结点颜色反转。求 q 次操作后每个结点的颜色。

💡
人话翻译:不要真的去翻转子树(每次 O(子树大小),q 次会超时)。
关键观察:一个结点被翻转的奇偶性,等于"它自己和它所有祖先被选中的次数之和"的奇偶性。因为"选中 a 会翻转 a 的整棵子树",等价于"只要 v 在 a 的子树里,v 就翻转一次"。
于是从根往下一遍累加就得到每个结点的翻转奇偶。

🔍 关键词提取

子树操作翻转奇偶祖先累加O(n+q)

已知条件

项目说明
输入n;n−1 个父结点;01 串;q;q 个被选结点
输出一行长度 n 的 01 串
数据范围n, q ≤ 10⁵
操作翻转以 a 为根的子树内所有颜色
便利条件父结点编号一定小于子结点编号

需要解决的问题

02
思维导图
整理解题思路的全貌
🔄 子树翻转 = 祖先计数累加
🧠 转化
每个结点只关心"被翻了几次"
奇偶性决定最终颜色
选中 a → a 的子树全部翻转
等价于"每个后代都 +1"
📐 累加公式
flip[v] = 翻转 v 的次数
flip[v] = Σ cnt[u](u 是 v 的祖先或自己)
递推:flip[v] = flip[父] + cnt[v]
按编号递增即可
✅ 输出
最终颜色 = 初始颜色 XOR (flip[v] % 2)
按编号顺序输出
0 表示白、1 表示黑
无需真的修改数组
⚠️ 易错点
真的模拟子树翻转(超时)
累加时用父结点的 cnt 而非 flip
忘记加上自己的 cnt
XOR 与 OR 混淆
03
样例手算推导
样例的完整推演

🧮 样例:n = 6,父结点 3 1 1 3 4,颜色 "100101"

先理清树的结构(结点 2~6 的父结点依次是 3、1、1、3、4)。

结点父结点
23
31
41
53
64

树形:1 → {3, 4};3 → {2, 5};4 → {6}

初始颜色(1 起):1=1、2=0、3=0、4=1、5=0、6=1。

1
统计操作次数 cnt

操作序列:1、3、2

cnt[1] = 1(被选 1 次)

cnt[3] = 1

cnt[2] = 1

其他 cnt = 0

cnt = {1:1, 2:1, 3:1}

2
按编号从 1 到 6 递推 flip

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}

3
按奇偶求最终颜色

结点 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"

📊 汇总表

结点初始色cntflipflip 奇偶最终色
1111奇0
2013奇1
3012偶0
4101奇0
5002偶0
6101奇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)——这正是"观察出可累加的不变量"带来的巨大优化。
04
解法对比
祖先计数 O(n+q) vs 真的翻转子树

⚔️ 解法对比

🟢 祖先计数 + 奇偶(推荐) 推荐

统计每个结点被选次数,从根往下累加得到翻转次数,取奇偶

  • 时间 O(n + q)
  • n = q = 10⁵ 时约 2 × 10⁵
  • 代码 20 行
  • 空间 O(n)
💡
核心两行:cnt[a]++(读操作时统计);flip[v] = flip[par[v]] + cnt[v](按编号递增递推)。利用了"父结点编号更小"这个条件,所以完全不需要建图、不需要 DFS。

🟠 真的翻转整棵子树

每次操作用 DFS 遍历子树并翻转颜色

  • 每次 O(子树大小),最坏 O(n)
  • q 次合计 O(nq) = 10¹⁰
  • 必然超时
  • 只能过 n,q ≤ 1000 的测试点
⚠️
注意数据分档:40% 的测试点 n, q ≤ 1000(可以暴力),但想满分必须 O(n + q)。看到"区间/子树整体操作"就要想到"能不能转化成差分或计数"。

📈 性能对比

方案复杂度可行性
祖先计数O(n + q)✅ 稳过
暴力翻转O(nq)❌ 超时
05
算法流程图
统计选次并自顶向下累加
开始读入 n、父结点数组 par、初始颜色串 s读入 q 个操作,对每个 a 执行 cnt[a] = cnt[a] + 1以结点 1 为起点:flip[1] = cnt[1]v 从 2 遍历到 nflip[v] = flip[par[v]] + cnt[v]输出颜色:初始色 XOR(flip[v] 的奇偶)结束v 加 1 处理下一个结点
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔄 子树翻转后的颜色

第一行输入 n,第二行输入父结点,第三行输入颜色串,第四行输入操作数与操作。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#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;
}
🔑
为什么"只统计次数"就够了?关键在于两次翻转等于没翻转——颜色只有黑/白两种,所以只有"翻转次数的奇偶性"影响结果。
而"v 被翻了几次"正好等于"v 的所有祖先(含自己)被选中的次数之和"——因为每次选中一个祖先,就会把 v 所在的整棵子树都翻一遍。把"整体操作"转化成"逐点计数",这就是本题的核心降维。

📖 关键几行怎么看

代码作用为什么这样写
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]);④ 用 % 判断奇偶而不用位运算(都对,但位运算更快)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
6
3 1 1 3 4
100101
3
1 3 2
010000题面样例
3
1 1
000
1
1
111翻转以根为根的整棵树,三个结点全变色
3
1 1
000
2
1 1
000同一结点选两次,等于没翻
2
1
00
1
1
11翻转整棵树(根为 1,子树含结点 2)
2
1
01
1
2
00只翻结点 2 的子树:结点 2 由 1 变 0
✅
自查清单:① 只统计次数吗?② 累加用了父的 flip 吗?③ 加了自身 cnt 吗?

🚨 易错点清单

⚠️
真模拟翻转:每次 O(子树大小),q 次可能达 10¹⁰。
⚠️
累加漏祖先:必须用 flip[par] 而不是 cnt[par]。
⚠️
漏掉自己:递推式里要有 + cnt[v]。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n + q)
空间复杂度
O(n)
n, q 最大
10⁵
运算量
约 2 × 10⁵

时间怎么算的?

空间都用在哪?

需要 par、cnt、flip 三个长度 n+1 的数组。

✅ 约 20 万次操作,瞬间完成。相比暴力翻转的 10¹⁰,快了五个数量级。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 核心观察
// 子树整体操作  <=>  每个后代被操作一次
// 所以只需统计"每个点被选中的次数",再从根往下累加

// 一般树(父结点编号不一定小于子结点)的做法
// 思路一样,只是累加要用拓扑序(BFS/DFS):
vector<int> order;                 // BFS 顺序
for (int u : order)                // 按拓扑序从根往下
    for (int v : children[u])
        flip[v] = flip[u] + cnt[v];

// 类似"区间整体操作"的差分技巧
// 一维数组区间加 -> 差分数组,最后做前缀和
// 树上的子树操作 -> 本题这种"祖先累加"
// 二者本质相同:把"范围操作"转成"端点标记 + 一次扫描"

// 常见变体
// - 子树加、子树赋值(配合欧拉序转成区间)
// - 路径操作(配合树上差分)
// - 多次整体反转(本题)

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
子树操作转计数祖先累加所有"整棵子树统一操作"的题
翻转只看奇偶两次抵消只有两种状态的反复操作
差分思想端点标记 + 一次扫描区间/子树批量操作
🌟
思考题:如果题目改成"每次把从某结点到根的路径上的颜色全部反转",还能用类似的技巧吗?(提示:可以——把"被路径覆盖的次数"累加,用树上差分:每次操作只需在 cnt[a]++,最后自底向上累加到根即可。注意方向变了:子树操作是"自顶向下累加",路径操作是"自底向上累加"。)