← 返回题目列表

Codeforces · 2237/H

H. 史莱姆和查询

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

给您一棵树,其顶点为 $$$n$$$,编号从 $$$1$$$ 到 $$$n$$$。史莱姆恰好占据了树的 $$$m$$$ 个顶点。保证由被占用的顶点导出的子图是连通的。

最初,史莱姆占据顶点 $$$s_1,s_2,\ldots,s_m$$$。

首先,我们在一系列顶点上定义一个函数 $$$f$$$。考虑一个序列 $$$a_1,a_2,\ldots,a_k$$$。有 $$$k$$$ 块食物。对于每个 $$$i$$$,第 $$$i$$$ 块食物位于顶点 $$$a_i$$$ 处。起初,只出现第一块食物。

史莱姆可以执行任意多次以下操作:

  • 移动。粘液将自身从当前占据的一个顶点移除并扩展到当前未占据的一个顶点。

    正式地,令 $$$S$$$ 为当前占用的顶点集。选择一个顶点 $$$u\in S$$$ 和一个顶点 $$$v\notin S$$$,并将 $$$S$$$ 替换为 $$$(S\setminus{u})\cup{v}$$$。操作完成后,$$$S$$$ 导出的子图仍必须是连通的。

  • 吃。如果第 $$$i$$$ 块食物已经出现,并且史莱姆当前占据顶点 $$$a_i$$$,则史莱姆可能会吃掉第 $$$i$$$ 块食物。如果 $$$1\le i \lt k$$$,则第 $$$(i+1)$$$ 块食物紧随其后出现。吃东西不会改变占用的顶点。

定义 $$$f([a_1,a_2,\ldots,a_k])$$$ 为最小数量 移动 史莱姆从最初占据的顶点 $$$s_1,s_2,\ldots,s_m$$$ 开始按顺序吃掉所有 $$$k$$$ 块食物所需的操作。

有 $$$q$$$ 查询。强制在线输入。输入给出编码值$$$p_1,p_2,\ldots,p_q$$$。设 $$$\mathrm{ans}_0=0$$$。对于每个 $$$i=1,2,\ldots,q$$$,第 $$$i$$$ 查询的实际顶点为 $$$c_i=((p_i-1+\mathrm{ans}_{i-1}) \bmod n)+1$$$,其中 $$$\mathrm{ans}_i=f([c_1,c_2,\ldots,c_i])$$$。

对于每个$$$i=1,2,\ldots,q$$$,输出$$$\mathrm{ans}_i$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$2\le m\le n\le 10^5$$$, $$$1\le q\le 10^5$$$) — 树中的顶点数、粘液占用的顶点数以及粘液的数量查询。

接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u,v\le n$$$, $$$u\ne v$$$),表示树的一条边。

下一行包含 $$$m$$$ 不同的整数 $$$s_1,s_2,\ldots,s_m$$$ ($$$1\le s_i\le n$$$) - 粘液最初占据的顶点。保证这些顶点产生一个连通的子图。

下一行包含 $$$q$$$ 整数 $$$p_1,p_2,\ldots,p_q$$$ ($$$1\le p_i\le n$$$) - 编码的查询顶点。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

保证所有测试用例的 $$$q$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出 $$$q$$$ 整数。第 $$$i$$$ 个整数应为 $$$\mathrm{ans}_i$$$。

示例

输入
复制

10
5 2 3
3 5
2 1
4 3
3 2
1 2
1 4 3
6 3 4
5 1
1 3
6 1
4 1
2 1
1 2 3
5 2 5 6
7 3 5
3 7
4 2
1 3
2 1
6 3
5 2
1 2 4
7 3 2 5 2
5 2 5
3 1
1 5
2 1
4 1
1 2
3 3 3 4 2
6 3 6
4 6
3 2
1 2
5 4
2 4
2 4 5
6 6 1 2 4 6
7 4 5
5 2
3 1
2 1
3 7
6 3
4 2
1 2 3 4
7 4 4 5 1
4 3 4
3 1
1 4
2 1
1 2 3
4 1 2 3
6 2 5
2 4
5 4
2 1
6 4
3 2
1 2
6 1 1 1 2
7 2 5
2 4
7 3
3 6
1 3
1 2
5 2
1 2
4 6 1 6 5
8 4 6
5 2
3 2
7 5
4 3
8 7
1 2
6 5
2 3 4 5
8 7 3 3 7 8

输出
复制

0 2 3
1 1 2 3
2 4 6 8 9
1 2 3 4 4
1 2 3 4 4 4
1 2 3 3 4
1 1 2 2
2 4 6 8 9
1 4 7 10 11
2 3 4 4 5 5

注意

在下面的解释中,下划线的顶点是经过一段时间后新占用的顶点。 移动,史莱姆吃食物的顶点以粗体显示。

在第一个测试用例中,解码后,食物按顺序出现在顶点 $$$1,4,5$$$ 处。最初,粘液占据$$$[1,2]$$$。

  1. 对于$$$[1]$$$,史莱姆已经占据顶点$$$\mathbf{1}$$$,因此$$$\mathrm{ans}_1=0$$$。
  2. 对于$$$[1,4]$$$,一个最佳过程是$$$[\mathbf{1},2]\to[2,\underline{3}]\to[3,\underline{\mathbf{4}}]$$$,因此$$$\mathrm{ans}_2=2$$$。
  3. 对于 $$$[1,4,5]$$$,一个最佳过程是 $$$[\mathbf{1},2]\to[2,\underline{3}]\to[3,\underline{\mathbf{4}}]\to[3,\underline{\mathbf{5}}]$$$,因此$$$\mathrm{ans}_3=3$$$。

在第二个测试用例中,解码后,食物按顺序出现在顶点 $$$5,3,6,2$$$ 处。最初,史莱姆占据$$$[1,2,3]$$$。

  1. 对于$$$[5]$$$,一个最佳过程是$$$[1,2,3]\to[1,3,\underline{\mathbf{5}}]$$$,因此$$$\mathrm{ans}_1=1$$$。
  2. 对于$$$[5,3]$$$,相同的过程还让史莱姆在顶点$$$\mathbf{3}$$$处吃东西,所以$$$\mathrm{ans}_2=1$$$。
  3. 对于$$$[5,3,6]$$$,一个最佳过程是$$$[1,2,3]\to[1,3,\underline{\mathbf{5}}]\to[1,3,\underline{\mathbf{6}}]$$$,因此$$$\mathrm{ans}_3=2$$$。
  4. 对于 $$$[5,3,6,2]$$$,一个最佳过程是 $$$[1,2,3]\to[1,3,\underline{\mathbf{5}}]\to[1,3,\underline{\mathbf{6}}]\to[1,\underline{\mathbf{2}},3]$$$,因此$$$\mathrm{ans}_4=3$$$。

在第三个测试用例中,解码后,食物按顺序出现在顶点$$$7,5,6,4,3$$$处。最初,史莱姆占据$$$[1,2,4]$$$。

  1. 对于$$$[7]$$$,一个最佳过程是$$$[1,2,4]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{7}}]$$$,因此$$$\mathrm{ans}_1=2$$$。
  2. 对于 $$$[7,5]$$$,一个最佳过程是 $$$[1,2,4]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{7}}]\to[1,\underline{2},3]\to[1,2,\underline{\mathbf{5}}]$$$,因此$$$\mathrm{ans}_2=4$$$。
  3. 对于 $$$[7,5,6]$$$,一个最佳过程是$$$[1,2,4]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{7}}]\to[1,\underline{2},3]\到[1,2,\underline{\mathbf{5}}]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{6}}]$$$,所以$$$\mathrm{ans}_3=6$$$。
  4. 对于 $$$[7,5,6,4]$$$,继续 $$$[1,3,\mathbf{6}]\to[1,\underline{2},3]\to[1,2,\underline{\mathbf{4}}]$$$,因此 $$$\mathrm{ans}_4=8$$$。
  5. 对于 $$$[7,5,6,4,3]$$$,继续 $$$[1,2,\mathbf{4}]\to[1,2,\underline{\mathbf{3}}]$$$,因此 $$$\mathrm{ans}_5=9$$$。

在第四个测试用例中,解码后,食物出现在顶点$$$3,4,5,2,1$$$处。

在第五个测试用例中,解码后,食物出现在顶点$$$6,1,3,5,2,4$$$处。

在第六个测试用例中,解码后,食物出现在顶点$$$7,5,6,1,4$$$处。