407512: GYM102821 D Divide a Tree

Fish has a tree with $$$N$$$ nodes numbered from $$$1$$$ to $$$N$$$, and for each node there is a label attached to it. These labels are integers ranging from $$$1$$$ to $$$N$$$. Now Fish wants to divide the tree into many parts and each part is a connected component in the tree. There are so many ways to achieve it, right? But now Fish defines a part as a good part if there is at least one label appears only in this part.

Please tell Fish how many good parts he can get at most in one division.

The first line of input contains an integer $$$T$$$, representing the number of test cases.

Then for each test case:

The first line contains one integer $$$N$$$ as mentioned above.

The second line contains $$$N$$$ integers, representing the label for each node.

Then $$$N - 1$$$ lines follow, each line containing two numbers $$$a, b$$$, which means that there is an edge connecting node $$$a$$$ and node $$$b$$$.

For each test case, you should output Case $$$x$$$: $$$y$$$, where $$$x$$$ indicates the case number starting from $$$1$$$, and $$$y$$$ is the number of good parts Fish can get at most in one division.

2
6
1 1 2 2 3 3
1 2
2 3
2 4
1 5
5 6
6
1 1 2 2 3 3
1 2
1 3
3 4
1 5
5 6

Case 1: 2
Case 2: 3

$$$1 \le T \le 100$$$

$$$1 \le N \le 10^5$$$

$$$1 \le a, b \le N$$$

For $$$90\%$$$ test cases: $$$N \le 1000$$$