Treeland and Viruses
Contest: Технокубок 2020 - Финал

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 format:
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 format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
7
1 2
1 3
2 4
2 5
3 6
3 7
3
2 2
4 1
7 1
1 3
2 2
4 3
7 1
1 3
3 3
1 1
4 100
7 100
1 2 3

Example output:
1 2
1 1
1 1 1

Editorial:
When processing a query, the key idea is to build a compressed version of the tree containing only some important vertices. We are not interested in vertices not belonging to any path between some $$$v_i$$$ and $$$u_i$$$. Furthermore, we can compress all chains in the tree by deleting all vertices with degree $$$< 2$$$ not listed in the query. To find all the important vertices in the compressed tree, we may do the following: sort all $$$v_i$$$ and $$$u_i$$$ by their entry time in DFS traversal of the tree, and then add LCA's of all neighbouring pairs in the sorted list.
To restore the edges, we will consider all important vertices in sorted order and maintain the path to the current vertex in a stack. When we process a vertex, we delete vertices from top of the stack until we get an ancestor of current vertex on top of the stack, then this ancestor is the parent of the current vertex in the compressed tree.
When we have the compressed tree, there are two approaches to determining the virus affecting each node:
• Run Dijkstra's algorithm. The distance for each vertex $$$v$$$ is the pair (the time when $$$v$$$ becomes infected, the index of a virus infecting $$$v$$$). For each initially infected vertex $$$v_i$$$ the initial distance is $$$(0,i)$$$. When processing a vertex with Dijkstra, we can try to infect all of its neighbours with the same virus.
• Use subtree DP. First of all, for each vertex we determine the virus from its subtree that will infecting it (not taking into account any viruses from above): it's either the virus in this vertex or the virus infecting one of its children. Then we may to the same thing in the other direction: push viruses down the tree and calculate whether they are infecting vertices faster than the viruses from the lower vertices.
In any case, each query is processed in $$$O((k + m) \log n)$$$.