← 返回题目列表

Codeforces · 1442/E

E. 黑色、白色和灰色树

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

给你一棵树,每个顶点颜色为白色、黑色或灰色。您可以通过选择单个连接组件中的顶点子集并从图中删除它们及其相邻边来从树中删除元素。唯一的限制是您不能同时选择包含白色和黑色顶点的子集。

从树中删除所有顶点所需的最少删除次数是多少?

输入

每个测试包含多个测试用例。第一行包含一个整数$$$t$$$ ($$$1 \le t \le 100\,000$$$),表示测试用例的数量,后面是测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$):树中的顶点数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_v$$$ ($$$0 \le a_v \le 2$$$):顶点的颜色。灰色顶点有$$$a_v=0$$$,白色有$$$a_v=1$$$,黑色有$$$a_v=2$$$。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u, v$$$ ($$$1 \le u, v \le n$$$):树边。

整个测试过程中所有 $$$n$$$ 的总和保证不超过 $$$200\,000$$$。

输出

对于每个测试用例,打印一个整数:解决问题的最少操作数。

示例

输入 #1

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

输出 #1

1
3
2
3

注意

在第一个测试用例中,两个顶点都是白色的,因此您可以同时删除它们。

在第二个测试用例中,三个操作就足够了。首先,我们需要删除两个黑色顶点(2 和 4),然后分别删除顶点 1 和 3。我们不能将它们一起删除,因为在删除顶点 2 后它们最终会出现在不同的连接组件中。

在第三个测试用例中,我们可以同时删除顶点1、2、3、4,因为其中三个是白色的,一个是灰色的。之后,我们可以删除顶点 5。

在第四个测试用例中,三个操作就足够了。解决该问题的方法之一是一次性删除所有黑色顶点,然后删除白色顶点 7,最后删除相连的白色顶点 1 和 3。