简答题 偏难
#21105

二叉树 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有一棵包含n个节点的二叉树,且根节点的编号为1。这棵二叉树任意一个节点要么是白色,要么是…

二叉树

时间限制:1.0 s

内存限制:512.0 MB

题面描述

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

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

输入格式

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

第二行n−1个正整数,第i(1≤i≤n−1) 个数表示编号为i+1 的节点的父亲节点编号,数据保证是一棵二叉树。

第三行一个长度为n的01 串,从左到右第i(1≤i≤n) 位如果为0,表示编号为i的节点颜色为白色,否则为黑色。

第四行一个正整数q,表示操作次数。

接下来q行每行一个正整数ai(1≤ai≤n),表示第i次操作选择的节点编号。

输出格式

输出一行一个长度为n的01 串,表示q次操作全部完成之后每个节点的颜色。从左到右第i(1≤i≤n) 位如果为0,表示编号为i的节点颜色为白色,否则为黑色。


输入样例

6
3 1 1 3 4
100101
3
1
3
2

输出样例

010000

样例解释

第一次操作后,节点颜色为:011010

第二次操作后,节点颜色为:000000

第三次操作后,节点颜色为:010000

数据范围

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 1e5+10; int n; int son[N][2]; int f[N],col[N],sum[N]; void dfs(int x,int now){ now+=sum[x]; if(now&amp;1)col[x]^=1; for(int i=0;i&lt;2;i++){ if(son[x][i]!=-1)dfs(son[x][i],now); } } int main(){ cin&gt;&gt;n; memset(son,-1,sizeof son); for(int i=2;i&lt;=n;i++){ cin&gt;&gt;f[i]; for(int j=0;j&lt;2;j++){ if(son[f[i]][j]==-1){ son[f[i]][j]=i; break; } } } string s; cin&gt;&gt;s; for(int i=1;i&lt;=n;i++){ col[i]=s[i-1]-'0'; } int q; cin&gt;&gt;q; while(q--){ int x; cin&gt;&gt;x; sum[x]+=1; } dfs(1,0); for(int i=1;i&lt;=n;i++){ cout&lt;&lt;col[i]; } cout&lt;&lt;"\n"; }</pre>
解析

①比较朴素的思路为建树,每次操作时执行DFS,将操作的结果处理,最终输出每个节点颜色,极端情况下每次操作遍历整棵树的话,复杂度O(nq),只能解决40%的数据。

②考虑到程序只要最终结果,因此中间结果没必要完全求得,取反操作的周期为2,具有奇偶性,因此每次操作X时,将X的位置打个标记,表示其将影响X下方的每个节点翻转一次,当所有操作标记完,执行DFS,从root=1出发,统计到达每个节点X时的标记的数量cnt,如果cnt为奇数,则改点颜色取反,否则保持原来颜色。这样只需要O(n+q)的复杂度。