CF1320E.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.

Treeland 有 $n$ 座城市，由 $n - 1$ 条双向道路连接，使得任意城市均可从其余任一城市到达；换言之，城市与道路构成一棵树。Treeland 正在为季节性病毒疫情做准备，目前正尝试评估多种感染情景。

在每种情景中，若干城市初始时被不同种类的病毒所感染。设第 $i$ 种情景中共有 $k_i$ 种病毒。记 $v_j$ 为病毒 $j$ 的初始感染城市，$s_j$ 为其传播速度。病毒的传播按轮次进行：先由病毒 $1$ 传播，接着是病毒 $2$，依此类推；当病毒 $k_i$ 完成一轮传播后，下一轮再次从病毒 $1$ 开始。

病毒 $j$ 的一次传播轮次按如下方式进行：对于每个在本轮开始时尚未被任何病毒感染的城市 $x$，若满足以下全部条件，则在本轮结束时它将被病毒 $j$ 感染：

• 城市 $y$ 在本轮开始时已被病毒 $j$ 感染；
• 城市 $x$ 与 $y$ 之间的路径上至多包含 $s_j$ 条边；
• 城市 $x$ 与 $y$ 之间路径上的所有城市（不包括 $y$）在本轮开始时均未被任何病毒感染。

一旦某城市被某种病毒感染，它将永久保持该病毒感染状态，且不能再被其他病毒所感染。当所有城市均已被感染时，传播过程终止。

你需要处理 $q$ 个相互独立的情景。每个情景由 $k_i$ 种病毒及 $m_i$ 个重要城市描述。对每个重要城市，请确定其最终被哪种病毒所感染。

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.

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— 表示 Treeland 中的城市数量。

接下来的 $n - 1$ 行描述道路。其中第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq n$）—— 表示由第 $i$ 条道路连接的两座城市的编号。保证所给的城市与道路构成的图是一棵树。

下一行包含一个整数 $q$（$1 \leq q \leq 2 \cdot 10^5$）—— 表示感染场景的数量。随后是 $q$ 个场景的描述。

第 $i$ 个场景的描述以一行开始，该行包含两个整数 $k_i$ 和 $m_i$（$1 \leq k_i, m_i \leq n$）—— 分别表示该场景中病毒种类的数量和重要城市的数量。保证 $\sum_{i = 1}^ q k_i$ 和 $\sum_{i = 1}^ q m_i$ 均不超过 $2 \cdot 10^5$。

接下来的 $k_i$ 行描述病毒种类。其中第 $j$ 行包含两个整数 $v_j$ 和 $s_j$（$1 \leq v_j \leq n$，$1 \leq s_j \leq 10^6$）—— 分别表示病毒种类 $j$ 的初始城市及其传播速度。保证同一场景中所有病毒种类的初始城市互不相同。

接下来的一行包含 $m_i$ 个互不相同的整数 $u_1, \ldots, u_{m_i}$（$1 \leq u_j \leq n$）—— 表示重要城市的编号。

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.

输出 $q$ 行。第 $i$ 行应包含 $m_i$ 个整数——即在第 $i$ 个场景结束时，城市 $u_1, \ldots, u_{m_i}$ 所感染的病毒种类的编号。