CF1320E Treeland and Viruses

Treeland 有 $n$ 个城市，这些城市通过 $n-1$ 条双向道路连接，使得任意两个城市之间都可以互相到达；换句话说，这些城市和道路构成了一棵树。Treeland 正在为季节性病毒流行做准备，目前他们正在评估不同的感染情景。 在每种情景下，有若干城市最初被不同的病毒种类感染。假设第 $i$ 个情景中有 $k_i$ 种病毒。我们用 $v_j$ 表示第 $j$ 种病毒的初始感染城市，用 $s_j$ 表示第 $j$ 种病毒的传播速度。病毒的传播按轮次进行：首先是病毒 $1$ 传播，然后是病毒 $2$，依次类推。病毒 $k_i$ 传播后，下一轮又从病毒 $1$ 开始。 第 $j$ 种病毒的每一轮传播过程如下：对于每个在本轮开始时尚未被任何病毒感染的城市 $x$，如果存在某个城市 $y$ 满足以下条件，则在本轮结束时 $x$ 会被病毒 $j$ 感染： - 城市 $y$ 在本轮开始时已被病毒 $j$ 感染； - 城市 $x$ 和 $y$ 之间的路径包含的边数不超过 $s_j$； - 路径上除 $y$ 外的所有城市在本轮开始时都未被任何病毒感染。 一旦城市被某种病毒感染，它将永久保持感染状态，且不会再被其他病毒感染。传播过程会一直持续，直到所有城市都被感染为止。 你需要处理 $q$ 个独立的情景。每个情景给定 $k_i$ 种病毒和 $m_i$ 个重要城市。对于每个重要城市，确定它最终会被哪种病毒感染。

第一行包含一个整数 $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$），表示重要城市的编号。

输出 $q$ 行。第 $i$ 行包含 $m_i$ 个整数，依次表示第 $i$ 个情景中每个重要城市 $u_1, \ldots, u_{m_i}$ 最终被哪种病毒感染（输出病毒种类的编号）。

由 ChatGPT 4.1 翻译