数据结构入门题

Time Limit: 2000 ms

Memory Limit: 131072kb

Description

  You are given a rooted Tree T (let's consider 1 as the root) of N nodes. Each node is associated with a value A[node]. You need to handle Q queries, each comprising one integer u. In each query you must report the number of distinct values in the subtree rooted at u. In other words, if you store all the values in the subtree rooted at u in a set, what would be the size of this set?

Input

  First line of input contains one integer T which indicates the number of test cases .

  The first line of each test case contains one integer N .

  Followed by 1 line with N integers representing A[1] , A[2] , … , A[N] .

  Then N-1 lines follow . The i-th of these lines contains 2 integers u and v , denoting one edge between u and v . It is guaranteed that the input data forms a tree .

  The next line contains 1 integer Q , the number of queries . 
  Each of the next Q lines contain 1 integer u described as above .

  1 ≤ T ≤ 5 
  1 ≤ N, Q ≤ 1e5 
  1 ≤ A[node] ≤ 1e5

Output

  For each query , print one integer in its own line .

Sample Input



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









8

Sample Output









1

Hint

None

Source

None

提交代码