A13322 | Treeland and Viruses

There are $n$ cities in Treeland connected with $n - 1$ bidirectional roads in such that a way that any city is reachable from any other; in other words, the graph of cities and roads is a tree. Treeland is preparing for a seasonal virus epidemic, and currently, they are trying to evaluate different infection scenarios.

In each scenario, several cities are initially infected with different virus species. Suppose that there are $k_i$ virus species in the $i$ -th scenario. Let us denote $v_j$ the initial city for the virus $j$ , and $s_j$ the propagation speed of the virus $j$ . The spread of the viruses happens in turns: first virus $1$ spreads, followed by virus $2$ , and so on. After virus $k_i$ spreads, the process starts again from virus $1$ .

A spread turn of virus $j$ proceeds as follows. For each city $x$ not infected with any virus at the start of the turn, at the end of the turn it becomes infected with virus $j$ if and only if there is such a city $y$ that:

- city $y$ was infected with virus $j$ at the start of the turn;
- the path between cities $x$ and $y$ contains at most $s_j$ edges;
- all cities on the path between cities $x$ and $y$ (excluding $y$ ) were uninfected with any virus at the start of the turn.

Once a city is infected with a virus, it stays infected indefinitely and can not be infected with any other virus. The spread stops once all cities are infected.

You need to process $q$ independent scenarios. Each scenario is described by $k_i$ virus species and $m_i$ important cities. For each important city determine which the virus it will be infected by in the end.

The first line contains a single integer $n$ ( $1 \leq n \leq 2 \cdot 10^5$ ) — the number of cities in Treeland.

The following $n - 1$ lines describe the roads. The $i$ -th of these lines contains two integers $x_i$ and $y_i$ ( $1 \leq x_i, y_i \leq n$ ) — indices of cities connecting by the $i$ -th road. It is guaranteed that the given graph of cities and roads is a tree.

The next line contains a single integer $q$ ( $1 \leq q \leq 2 \cdot 10^5$ ) — the number of infection scenarios. $q$ scenario descriptions follow.

The description of the $i$ -th scenario starts with a line containing two integers $k_i$ and $m_i$ ( $1 \leq k_i, m_i \leq n$ ) — the number of virus species and the number of important cities in this scenario respectively. It is guaranteed that $\sum_{i = 1}^ q k_i$ and $\sum_{i = 1}^ q m_i$ do not exceed $2 \cdot 10^5$ .

The following $k_i$ lines describe the virus species. The $j$ -th of these lines contains two integers $v_j$ and $s_j$ ( $1 \leq v_j \leq n$ , $1 \leq s_j \leq 10^6$ ) – the initial city and the propagation speed of the virus species $j$ . It is guaranteed that the initial cities of all virus species within a scenario are distinct.

The following line contains $m_i$ distinct integers $u_1, \ldots, u_{m_i}$ ( $1 \leq u_j \leq n$ ) — indices of important cities.

Print $q$ lines. The $i$ -th line should contain $m_i$ integers — indices of virus species that cities $u_1, \ldots, u_{m_i}$ are infected with at the end of the $i$ -th scenario.