Tree and Queries 14

The tree has $N$ vertices numbered from 1 to $N$. Every edge has weight 1.

Write a program that processes the following query.

• k v1 r1 v2 r2 ... vk rk: A vertex $x$ satisfies condition $i$ if its distance from $v_i$ is at most $r_i$. Among all vertices in the tree, count the vertices that satisfy at least $k-1$ of the $k$ conditions in the query.

The first line contains $N$ ($1 \le N \le 100{,}000$).

Each of the next $N-1$ lines contains two vertex numbers $u$ and $v$ connected by an edge ($1 \le u, v \le N$).

The next line contains $M$ ($1 \le M \le 300{,}000$), the number of queries.

Each query spans $k+1$ lines, not one line. The $M$ queries follow in this format. ($1 \le v_i \le N$, $0 \le r_i < N$, $1 \le k$)

The sum of $k$ over all queries does not exceed $300000$.

Print the answer to each query on its own line.