黑、白、灰树

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

给定一棵树，每个顶点被染成白色、黑色或灰色。

一次操作中，你需要先选定当前森林中的一个连通块，再选择这个连通块中的一个非空顶点子集，删除这些顶点以及与它们相邻的所有边。所选子集不能同时包含白色顶点和黑色顶点；灰色顶点可以与任意一种颜色一起选择。

求删除所有顶点所需的最少操作次数。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

对于每个测试用例：

• 第一行包含一个整数 $n$，表示树的顶点数；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。$a_v=0$ 表示灰色，$a_v=1$ 表示白色，$a_v=2$ 表示黑色；
• 接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示树中有一条连接顶点 $u,v$ 的边。

保证所有测试用例的 $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$，共三次操作。

第三个测试用例中，可以先一起删除顶点 $1,2,3,4$，再删除顶点 $5$。

第四个测试用例的一种最优方案是：先删除所有黑色顶点，再删除白色顶点 $7$，最后一起删除仍连通的白色顶点 $1,3$。

数据范围

对于所有数据，$1\le t\le 100\,000$，$1\le n\le 200\,000$，$0\le a_v\le 2$，所有测试用例的 $n$ 之和不超过 $200\,000$；输入保证给出的图是一棵树。

各子任务按顺序累积包含前面的限制层级。