Tree and Query 15

There is a tree with $N$ vertices. The vertices are numbered from 1 to $N$. Every edge has weight 1.

Write a program that handles the queries below.

• k v1 r1 v2 r2 ... vk rk: A vertex $x$ satisfies condition $i$ if its distance to $v_i$ is at most $r_i$. Print the number of vertices in the tree that satisfy at least one of the $k$ conditions in the query.

The first line contains an integer $N$ ($1 \le N \le 100{,}000$). The next $N-1$ lines each contain two vertices $u$ and $v$ connected by an edge ($1 \le u, v \le N$).

The next line contains an integer $M$ ($1 \le M \le 300{,}000$). Each query does not fit on one line. Each query is split across $k+1$ lines, as shown in the sample input. Constraints: $1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$.

The sum of all $k$ values in the queries does not exceed 300000.

For each query, print the result on its own line.