#CW80. 森林染色(forest)

森林染色(forest)

题目描述

给定一棵有 nn 个顶点的树。顶点颜色为灰、白、黑,分别用 0,1,20, 1, 2 表示。

一次操作中,在当前森林的一个连通块里选择一个非空顶点集合并删除这些顶点以及相邻边。被选择的集合不能同时包含白色和黑色顶点,灰色顶点可以与任意颜色一起选择。删除后剩余图可以分裂成多个连通块。求删除所有顶点所需的最少操作次数。

所选顶点集合本身不要求连通,只需这些顶点在操作前属于同一个连通块。

输入格式

从 forest.in 文件中读入。

第一行给出测试用例数 tt,满足 1≤t≤1000001 \le t \le 100000。每组第一行给出 nn,满足 1≤n≤2000001 \le n \le 200000,且所有测试用例的 nn 之和不超过 200000200000。第二行给出 nn 个颜色值 ai∈{0,1,2}a_i \in \{0, 1, 2\}。接下来 n−1n - 1 行给出树边 u,vu, v,满足 1≤u,v≤n1 \le u, v \le n。

输出格式

向 forest.out 文件中输出。

对每个测试用例输出一行最少操作次数。

样例 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

数据范围

所有输入数据均为整数。

本题采用子任务捆绑计分:通过一个子任务的全部测试点,才能获得该子任务的分数。

子任务 分值 测试点 附加条件
1 20 1∼41 \sim 4 n≤10n \le 10
2 25 5∼95 \sim 9 树是一条路径
3 10∼1410 \sim 14 只出现白色和黑色,即 ai∈{1,2}a_i \in \{1, 2\}
4 30 15∼2015 \sim 20 无额外限制