CF1442E.Black, White and Grey Tree

You are given a tree with each vertex coloured white, black or grey. You can remove elements from the tree by selecting a subset of vertices in a single connected component and removing them and their adjacent edges from the graph. The only restriction is that you are not allowed to select a subset containing a white and a black vertex at once.

What is the minimum number of removals necessary to remove all vertices from the tree?

你被给定一棵树，其中每个顶点被染成白色、黑色或灰色。你可以通过选择某个连通分量中的一组顶点，并将这些顶点及其关联的边从图中移除，来删除树中的元素。唯一的限制是：你不能同时选择一个包含白色顶点和黑色顶点的子集。

要移除树中的所有顶点，所需的最少删除操作次数是多少？

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 100\,000$), denoting the number of test cases, followed by a description of the test cases.

The first line of each test case contains an integer $n$ ($1 \le n \le 200\,000$): the number of vertices in the tree.

The second line of each test case contains $n$ integers $a_v$ ($0 \le a_v \le 2$): colours of vertices. Gray vertices have $a_v=0$, white have $a_v=1$, black have $a_v=2$.

Each of the next $n-1$ lines contains two integers $u, v$ ($1 \le u, v \le n$): tree edges.

The sum of all $n$ throughout the test is guaranteed to not exceed $200\,000$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, print one integer: the minimum number of operations to solve the problem.

对于每个测试用例，输出一个整数：解决该问题所需的最少操作次数。

In the first test case, both vertices are white, so you can remove them at the same time.

In the second test case, three operations are enough. First, we need to remove both black vertices (2 and 4), then separately remove vertices 1 and 3. We can't remove them together because they end up in different connectivity components after vertex 2 is removed.

In the third test case, we can remove vertices 1, 2, 3, 4 at the same time, because three of them are white and one is grey. After that, we can remove vertex 5.

In the fourth test case, three operations are enough. One of the ways to solve the problem is to remove all black vertices at once, then remove white vertex 7, and finally, remove connected white vertices 1 and 3.

在第一个测试用例中，两个顶点均为白色，因此可以同时移除它们。

在第二个测试用例中，三次操作即足够。首先需同时移除两个黑色顶点（2 和 4），然后分别移除顶点 1 和 3。我们不能将它们同时移除，因为在移除顶点 2 后，顶点 1 和 3 将位于不同的连通分量中。

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

在第四个测试用例中，三次操作即足够。一种可行的解法是：首先一次性移除所有黑色顶点；接着移除白色顶点 7；最后移除连通的白色顶点 1 和 3。