A13941 | $Black, White and Grey Tree$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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$ .

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

输入 #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

C++ 编辑器

输入

输出