Treeland and Viruses

3000ms

524288K

Description:

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.

Input:

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.

Output:

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.

Sample Input:

Sample Output:

1 2
1 1
1 1 1

Informação

Provedor Codeforces

Código CF1320E