← 返回题目列表

Codeforces · 1975/E

E. 链式查询

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 顶点组成的树,编号从 $$$1$$$ 到 $$$n$$$。最初,所有顶点都被涂成白色或黑色。

系统会要求您执行 $$$q$$$ 查询:

- “u”— 切换顶点 $$$u$$$ 的颜色(如果是白色,则将其更改为黑色,反之亦然)。

每次查询后,您应该回答所有黑色顶点是否形成一条链。也就是说,存在两个黑色顶点,使得它们之间的简单路径经过所有黑色顶点并且仅经过黑色顶点。具体来说,如果只有一个黑色顶点,它们就会形成一条链。如果没有黑色顶点,它们就不会形成链。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\leq t\leq 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1\leq n,q\leq 2\cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$c_1,c_2,\ldots,c_n$$$ ($$$c_i \in \{ \mathtt{0}, \mathtt{1} \}$$$) - 顶点的初始颜色。 $$$c_i$$$ 表示顶点 $$$i$$$ 的颜色,其中 $$$\mathtt{0}$$$ 表示白色,$$$\mathtt{1}$$$ 表示黑色。

接下来是 $$$n - 1$$$ 行,每行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i,y_i \le n$$$),表示顶点 $$$x_i$$$ 和 $$$y_i$$$ 之间的一条边。保证这些边形成一棵树。

接下来的 $$$q$$$ 行每行包含一个整数 $$$u_i$$$ ($$$1 \le u_i \le n$$$),表示需要切换顶点 $$$u_i$$$ 的颜色。

保证所有测试用例的 $$$n$$$ 和 $$$q$$$ 之和分别不超过 $$$2\cdot 10^5$$$。

输出

对于每个查询,如果黑色顶点形成链,则输出“是”,否则输出“否”。

在任何情况下都可以输出“Yes”和“No”(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应)。

示例

输入 #1

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

输出 #1

No
No
Yes
Yes
No

输入 #2

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

输出 #2

Yes
No
Yes
Yes
Yes
Yes
No
No
Yes

注意

在第二个测试用例中,顶点的颜色如下:

初始树:

第一个查询切换顶点 $$$4$$$ 的颜色:

第二个查询切换顶点 $$$3$$$ 的颜色:

第三个查询切换顶点 $$$2$$$ 的颜色:

第四个查询切换顶点 $$$5$$$ 的颜色: