1026: SYH’s Easy Tree Problem

SYH loves researching an interesting but easy data structure --- Tree. Assume there are n nodes on the tree. SYH paints all the nodes on the tree with color c_i firstly. Then, he will ask you q questions in the form of x_i and k_i: How many colors of nodes are no less than k_i in the sub-tree of the node x_i.

The first line conatins an integer T, means the number of test cases. For each test case, the first line contains two integers n and q. The second line contains n integers describing c₁~c_n. Then, n-1 lines contain two integers a_i, b_i in each, expressing the tree, while there is a path connecting a_i and b_i with one another. Then q lines contain two integers x_i, k_i in each, meaning the questions.

For each test case ouput “Case: #x:” in a single line. x is the test case number (starting from 1). Then q lines of the following answer.

1

8 4
1 3 1 8 8 3 1 8
1 2
1 6
5 6
8 6
2 3
4 2
2 7
2 2
6 3
1 3
2 1

Case #1: 
1
0
2
3