题目详情题解（0）讨论（0）提交记录（0）

AT_njpc2017_h.白黒ツリー

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给出N个顶点的有根的树。在各个顶点编号为1, 2,…N，顶点1是这根树的根。边全部是无向边，第i个( 2≤i≤N)顶点的父母是p[i]

最初，各顶点涂成白色或黑色，第i个顶点(1≤i≤N)初始的颜色为C[i]，

C[i]=0时白色，C[i]=1的时候是黑色。

因为有Q个查询，所以请按顺序处理。查询有以下两种，输入形式和查询内容如下：

1.输入1 u：把顶点u作为根的部分树包含的全部的顶点的颜色使之反转。

2.输入2 u v：从顶点u到顶点v，如果能交替通过白色顶点和黑色顶点到达YES，不然就输出NO。最初的颜色是白色还是黑色都可以。

输入格式

（输入是标准的以下形式）

N

p[2]

p[3]

...

p[n]

c[1]

c[2]

...

c[n]

Q

查询[1]

查询[2]

...

查询[Q]

输出格式

对于2 u v格式的查询，回答按给出的顺序每行输出1个。

约定

输入全部是整数

2≤N≤10^5

1≤p[i]≤N

C[i]=0或1

1≤Q≤10^5

输入的树一定连接

当查询为1 u时，1≤u≤N 1≤u≤N

当查询为2 u v时,1≤u,v≤N,且u≠v。

确保至少存在一个格式2 u v的查询。

输入输出样例

  • 输入#1

    6
1
1
2
2
3
0
1
0
0
1
1
10
2 4 1
2 4 3
2 1 2
1 2
2 4 1
1 3
1 5
2 1 6
1 1
2 5 4

    输出#1

    YES
NO
YES
NO
YES
YES

  • 输入#2

    7
1
2
3
3
5
6
0
0
1
0
0
1
1
7
2 1 4
2 4 2
2 4 5
2 4 6
2 6 1
2 7 1
2 2 6

    输出#2

    NO
YES
YES
YES
NO
NO
YES

  • 输入#3

    2
1
0
1
11
2 1 2
2 2 1
1 2
2 1 2
2 2 1
1 1
2 1 2
2 2 1
1 2
2 1 2
2 2 1

    输出#3

    YES
YES
NO
NO
NO
NO
YES
YES

  • 输入#4

    5
1
2
3
4
0
1
0
1
0
11
2 1 2
2 1 4
2 3 1
2 5 1
2 4 5
1 3
2 1 2
2 1 4
2 3 1
2 5 1
2 4 5

    输出#4

    YES
YES
YES
YES
YES
YES
NO
NO
NO
YES

  • 输入#5

    9
4
2
6
8
1
4
1
8
0
0
1
0
0
1
1
1
0
2
2 9 8
2 9 4

    输出#5

    YES
YES

输入解题思路，AI测评打分。不知道怎么写?

首页