3055: Counting On A Tree Again

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. $\left| {a_{i}-b_{i}} \right| \leq k$.
3. The $j_{th}$ node is an ancestor of the $i_{th}$ 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 \leq n \leq 2*10^{4})$, the number of vertices.

The following $n-1$ lines, each contains two integers $u, v (1 \leq u, v \leq 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 $i_{th}$ integer $a_{i}$ is the value of the $i_{th}$ node.

The next line contains an integer $q(1 \leq q \leq 10^{5})$, the number of queries.

The following $m$ lines, each contains two integers $x (1 \leq x \leq 2*10^{4}), k(1 \leq k \leq 2*10^{4})$,  representing the queries.

For each query print the answer.

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

4
1