← 返回题目列表

Codeforces · 1320/E

E. 林地和病毒

中文机器翻译题面 查看原题

Treeland 有 $$$n$$$ 个城市与 $$$n - 1$$$ 双向道路相连,这样任何城市都可以从任何其他城市到达;换句话说,城市和道路的图是一棵树。 Treeland 正在为季节性病毒流行做准备,目前他们正在尝试评估不同的感染情况。

在每种情况下,几个城市最初感染了不同的病毒种类。假设第 $$$i$$$ 个场景中有 $$$k_i$$$ 个病毒种类。让我们将 $$$v_j$$$ 表示病毒 $$$j$$$ 的初始城市,$$$s_j$$$ 表示病毒 $$$j$$$ 的传播速度。病毒的传播是轮流发生的:首先病毒 $$$1$$$ 传播,然后病毒 $$$2$$$ 传播,依此类推。病毒$$$k_i$$$传播后,该过程再次从病毒$$$1$$$开始。

病毒$$$j$$$ 的传播过程如下。对于每个城市 $$$x$$$ 在回合开始时未感染任何病毒,在回合结束时它会感染病毒 $$$j$$$ 当且仅当存在这样一个城市 $$$y$$$ 时:

- 城市$$$y$$$在回合开始时感染了病毒$$$j$$$;
- 城市 $$$x$$$ 和 $$$y$$$ 之间的路径最多包含 $$$s_j$$$ 边;
- 城市 $$$x$$$ 和 $$$y$$$ 之间路径上的所有城市(不包括 $$$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}$$$ 感染的病毒种类索引。

示例

输入 #1

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

输出 #1

1 2
1 1
1 1 1