You are given an undirected tree (a connected acyclic undirected graph) of n vertices rooted at 1. Vertices are numbered from 1 to n. The i
th node has the value a
i.
Then there are q queries, each of them contains two integers: x,k. For each query, you are required to count how many pairs of (i,j) that satisfy the following condition:
1. a
i= x.
2
. |ai− aj| ≤ k. 3. The jth node is an ancestor of the ith node.
输入描述:
The first line contains an integer number T, the number of test cases.
For each test case :
The first line contains an integer n(1 ≤ n ≤ 2*104), the number of vertices.
The following n − 1 lines, each contains two integers u,v(1 ≤ u,v ≤ n), which means there is an edge between u and v.
It is guaranteed that these edges denote a tree.
The next line contains n integers, the itℎinteger ai(ai ≤ n)is the value of the ith node.
The next line contains an integer q(1 ≤ q ≤ 105), the number of queries.
The following m lines, each contains two integers x(1 ≤ x ≤ 2*104),k(1 ≤ k ≤ 2*104), representing the queries.
输出描述:
For each query print the answer.
示例1
输入
复制
1
8
1 2
1 3
2 4
2 5
3 6
6 7
6 8
1 2 2 4 2 5 8 6
2
2 1
6 3