P6626 [NOI Qualifier Joint Contest 2020 B Volume] Message Passing

Given a tree-shaped social network with $n$ people (numbered from $1$ to $n$). If a person receives a message on some day, then on the next day they will pass the message to all people who have a direct social relationship with them. Now there are $m$ queries. In each query, assume that person $x$ receives a message on day $0$. Please compute how many people newly receive this message on day $k$ (that is, people who have received this message before day $k$ are not counted). Different queries do not affect each other.

**This problem contains multiple sets of testdata.** The first line contains an integer $T$, the number of test cases. For each test case: The first line contains two integers $n, m$, representing the number of people in the tree-shaped social network and the number of queries. The next $n - 1$ lines each contain two integers $a, b$, indicating that there is a direct social relationship between person $a$ and person $b$. It is guaranteed that the input forms a tree-shaped social network. The next $m$ lines each contain two integers $x, k$, as described in the statement.

For each test case, output $m$ lines, each containing one integer representing the answer to the query.

**Sample Explanation** For the first query, the only person who newly receives the message on day $1$ is person $2$. For the second query, the people who newly receive the message on day $1$ are persons $1$ and $3$, and the person who newly receives the message on day $2$ is person $4$. **Constraints and Notes** For test point $1$: $1\le n, m\le 10$. For test point $2$: $1\le n, m\le 100$. For test point $3$: $1\le n, m\le 1000$. For test points $4\sim6$: $1\le n, m\le 10^5, k\le 20$. For test points $7\sim10$: $1\le n, m\le 10^5$. For all test points: $1\le T\le 5, 1\le x\le n, 0\le k < n$. Translated by ChatGPT 5