题目描述

小杨有⼀棵包含 $n$ 个节点的二叉树，且根节点的编号为 $1$。这棵二叉树任意⼀个节点要么是白色，要么是黑色。之后小杨会对这棵二叉树进行 $q$ 次操作，每次小杨会选择⼀个节点，将以这个节点为根的子树内所有节点的颜色反转，即黑色变成白色，白色变成黑色。

小杨想知道 $q$ 次操作全部完成之后每个节点的颜色。

输入格式

第⼀行一个正整数 $n$，表示二叉树的节点数量。

第二行 $(n-1)$ 个正整数，第 $i$（$1\le i\le n-1$）个数表示编号为 $(i+1)$ 的节点的父亲节点编号，数据保证是⼀棵二叉树。

第三行一个长度为 $n$ 的 $\text{01}$ 串，从左到右第 $i$（$1\le i\le n$）位如果为 $\text{0}$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。

第四行⼀个正整数 $q$，表示操作次数。

接下来 $q$ 行每行⼀个正整数 $a_i$（$1\le a_i\le n$），表示第 $i$ 次操作选择的节点编号。

输出格式

输出一行一个长度为 $n$ 的 $\text{01}$ 串，表示 $q$ 次操作全部完成之后每个节点的颜色。从左到右第 $i$（$1\le i\le n$） 位如果为 $\text{0}$，表示编号为 $i$ 的节点颜色为白色，否则为黑色。

输入输出样例 #1

输入 #1

6
3 1 1 3 4
100101
3
1
3
2

输出 #1

010000

说明/提示

样例解释

第一次操作后，节点颜色为：$\text{011010}$

第二次操作后，节点颜色为：$\text{000000}$

第三次操作后，节点颜色为：$\text{010000}$

数据范围

子任务编号	得分	$n$	$q$	特殊条件
$1$	$20$	$\le 10^5$	$\le 10^5$	对于所有 $i\ge 2$，节点 $i$ 的父亲节点编号为 $i-1$
$2$	$40$	$\le 1000$	$\le 1000$
$3$	$40$	$\le 10^5$	$\le 10^5$

对于全部数据，保证有 $n,q\le 10^5$。

提交链接

二叉树

思路分析

暴力搜索(40分)

读取输入

cin >> n; // 读取二叉树的结点个数
for(int i = 2; i <= n; i++) {
    cin >> f[i];  // 读取每个节点的父节点编号
}
cin >> color;
color = ' ' + color;  // 让 color[1] 对应编号 1（为了方便索引）
cin >> q;

• $n$ 是二叉树的节点数，编号从 $1$ 到 $n$。
• $f[i]$ 记录 编号为 $i$ 的节点的父节点（即 $f[i]$ 是 $i$ 的直接父节点）。
• $color$ 是一个 $01$ 字符串，表示初始颜色。
• $q$ 是操作次数。

记录操作次数

while(q--) {  
    cin >> x;  // 选择节点 x 作为操作的根
    num[x] = (num[x] + 1) % 2;  // 记录节点 x 被操作的奇偶性
}

$num[x]$ 记录以 $x$ 为根的子树被操作的次数的奇偶性：

• 如果 $num[x]$ 是偶数，说明 $x$ 的子树 颜色未变。
• 如果 $num[x]$ 是奇数，说明 $x$ 的子树 颜色被翻转了一次。

遍历所有节点并计算最终颜色

for(int i = 1; i <= n; i++) {
    sum = 0;
    dfs(i);  // 计算 i 节点受到多少次翻转影响
    if(sum & 1) {  // 如果翻转次数是奇数
        if(color[i] == '1') color[i] = '0';
        else color[i] = '1';
    }
}

核心思想：

• 遍历所有 $i$，计算 $i$ 这个节点从 它自身到根节点 经过的 翻转次数 $sum$。
• 如果 $sum$ 是奇数，就翻转 $i$ 这个节点的颜色。

计算 $i$ 受到的翻转次数

void dfs(int x) {
    if(num[x]) sum++;  // 如果 x 这个节点被操作了，就增加翻转次数
    if(f[x] == 0) return;  // 递归终止：已经到达根节点
    dfs(f[x]);  // 继续递归到父节点
}

递归 $dfs(x)$：

• 如果 $x$ 本身是翻转点（$num[x]==1$），$sum++$。
• 继续向 $f[x]$（父节点）递归，直到到达根节点。
• 这样 $sum$ 记录的是 从 $x$ 到根节点的所有翻转次数。

输出最终颜色

for(int i = 1; i <= n; i++)
    cout << color[i];

直接输出所有节点最终的颜色。

存在的问题

$dfs(i)$ 重复计算了很多次。

• 每个 $i$ 都要从自己走到根，而 有些 $i$ 的路径是重复的，造成大量冗余计算。
• 树高最多是 $O(n)$，最坏情况下变成 $O(n^2)$。如果树是链状结构，则 $dfs(i)$ 的调用深度最坏是 $n$，遍历所有 $n$ 个节点就会导致 $O(n^2)$ 复杂度。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 9;

int n , q , f[MAX_N] , x , num[MAX_N] , sum;
string color;

void dfs(int x)
{
    if(num[x])
        sum++;
    if(f[x] == 0)
        return;
    dfs(f[x]);
    
}

int main()
{
    cin >> n; //二叉树的结点个数
    for(int i = 2; i <= n; i++)
        cin >> f[i];  //f[i]:结点i的父亲结点的编号
    
    cin >> color;
    color = ' ' + color;  //color[i]：编号为i的结点的颜色，color[i]=1为黑色 color[i]=0为白色

    cin >> q;

    while(q--)  //q次询问
    {
        cin >> x;  //选择编号为x的结点
        num[x] = (num[x] + 1) % 2;  //记录根结点为x的子树操作的次数
    }

    for(int i = 1; i <= n; i++)
    {
        sum = 0;
        dfs(i);
        if(sum & 1)
        {
            if(color[i] == '1')
                color[i] = '0';
            else
                color[i] = '1';
        }
    }
    for(int i = 1; i <= n; i++)
        cout << color[i];
    return 0;
}

搜索优化(100分)

改进点：

1. 改进翻转标记方式

   • 仍然使用 $num[x]$ 记录操作次数，但不再逐个节点 $DFS(i)$ 计算 $sum$。
   • 采用 子树 DFS 传播翻转状态，避免重复计算 $sum$。

2. 高效的 DFS 处理方式

   • 构建子树关系：G[f[i]].push_back(i) 记录子节点，而不是用 f[x] 记录父节点。
   • 从根遍历一次 DFS 传递翻转状态：
     • $check$ 变量标记当前节点是否应被翻转。
     • 遍历整个子树，每个节点仅访问一次，避免重复计算。

3. 时间复杂度分析

   • 树的遍历是 $O(n)$
   • 建树 $O(n)$。
   • 一次 DFS 处理整个树 $O(n)$。
   • 总时间复杂度 $O(n)$。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 9;

int n , q , f[MAX_N] , x , num[MAX_N] , sum;
string color;
vector<int>G[MAX_N];

void dfs(int x)
{
    if(num[x])
        sum++;
    if(f[x] == 0)
        return;
    dfs(f[x]);
}

void dfs(int x , bool check)
{
    
    if(check && num[x])   //check为父结点带来的影响  num[x]为本身是否需要操作
        check = false;
    else if(!check && num[x] || check && !num[x])
        check = true;
    
    if(check)
    {
        if(color[x] == '1')
            color[x] = '0';
        else
            color[x] = '1';
    }

    for(auto it : G[x])
        dfs(it , check);
}

int main()
{
    cin >> n; //二叉树的结点个数
    for(int i = 2; i <= n; i++)
    {
        cin >> f[i];  //f[i]:结点i的父亲结点的编号
        G[f[i]].push_back(i);  //儿子存储法
    }
    
    cin >> color;
    color = ' ' + color;  //color[i]：编号为i的结点的颜色，color[i]=1为黑色 color[i]=0为白色

    cin >> q;

    while(q--)  //q次询问
    {
        cin >> x;  //选择编号为x的结点
        num[x] = (num[x] + 1) % 2;  //记录根结点为x的子树操作的次数
    }

    dfs(1 , false);

    for(int i = 1; i <= n; i++)
        cout << color[i];
    return 0;
}