CF2237H.Slime and Queries

You are given a tree with $n$ vertices numbered from $1$ to $n$. A slime occupies exactly $m$ vertices of the tree. It is guaranteed that the subgraph induced by the occupied vertices is connected.

Initially, the slime occupies vertices $s_1,s_2,\ldots,s_m$.

First, we define a function $f$ on a sequence of vertices. Consider a sequence $a_1,a_2,\ldots,a_k$. There are $k$ pieces of food. For each $i$, the $i$-th piece of food is located at vertex $a_i$. At first, only the first piece of food appears.

The slime may perform the following operations any number of times:

• Move. The slime removes itself from one currently occupied vertex and expands to one currently unoccupied vertex.

  Formally, let $S$ be the current set of occupied vertices. Choose a vertex $u\in S$ and a vertex $v\notin S$, and replace $S$ with $(S\setminus{u})\cup{v}$. After the operation, the subgraph induced by $S$ must still be connected.

• Eat. If the $i$-th piece of food has appeared and the slime currently occupies vertex $a_i$, then the slime may eat the $i$-th piece of food. If $1\le i \lt k$, the $(i+1)$-th piece of food appears immediately after that. Eating does not change the occupied vertices.

Define $f([a_1,a_2,\ldots,a_k])$ as the minimum number of Move operations needed for the slime to eat all $k$ pieces of food in order, starting from the initial occupied vertices $s_1,s_2,\ldots,s_m$.

There are $q$ queries. The input is forced online. The input gives encoded values $p_1,p_2,\ldots,p_q$. Let $\mathrm{ans}_0=0$. For each $i=1,2,\ldots,q$, the actual vertex of the $i$-th query is $c_i=((p_i-1+\mathrm{ans}_{i-1}) \bmod n)+1$, where $\mathrm{ans}_i=f([c_1,c_2,\ldots,c_i])$.

For each $i=1,2,\ldots,q$, output $\mathrm{ans}_i$.

给你一棵有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。一只史莱姆恰好占据该树中的 $m$ 个顶点。保证这些被占据顶点所诱导出的子图是连通的。

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

首先，我们定义一个作用于顶点序列的函数 $f$。考虑一个顶点序列 $a_1,a_2,\ldots,a_k$。共有 $k$ 份食物；其中第 $i$ 份食物位于顶点 $a_i$。最初，仅有第 $1$ 份食物出现。

史莱姆可任意多次执行以下两种操作：

• 移动（Move）：史莱姆从当前被占据的一个顶点上撤离，并扩展至一个当前未被占据的顶点。
  形式化地，设 $S$ 为当前被占据顶点集合。选择一个顶点 $u\in S$ 和一个顶点 $v\notin S$，并将 $S$ 替换为 $(S\setminus\{u\})\cup\{v\}$。操作后，$S$ 所诱导的子图仍必须保持连通。

• 进食（Eat）：若第 $i$ 份食物已出现，且史莱姆当前正占据顶点 $a_i$，则史莱姆可吃掉第 $i$ 份食物。若 $1\le i < k$，则在吃掉第 $i$ 份食物后，第 $(i+1)$ 份食物会立即出现。进食操作不改变被占据的顶点集合。

定义 $f([a_1,a_2,\ldots,a_k])$ 为：从初始占据顶点集 $s_1,s_2,\ldots,s_m$ 出发，按顺序吃完全部 $k$ 份食物所需的最少 移动（Move） 操作次数。

共有 $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$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $q$ ($2\le m\le n\le 10^5$, $1\le q\le 10^5$) — the number of vertices in the tree, the number of vertices occupied by the slime, and the number of queries.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1\le u,v\le n$, $u\ne v$), denoting an edge of the tree.

The next line contains $m$ distinct integers $s_1,s_2,\ldots,s_m$ ($1\le s_i\le n$) — the vertices initially occupied by the slime. It is guaranteed that these vertices induce a connected subgraph.

The next line contains $q$ integers $p_1,p_2,\ldots,p_q$ ($1\le p_i\le n$) — the encoded query vertices.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $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$。

For each test case, output $q$ integers. The $i$-th integer should be $\mathrm{ans}_i$.

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

In the explanations below, the underlined vertex is the newly occupied vertex after a Move, and vertices where the slime eats food are written in bold.

In the first test case, after decoding, the food appears at vertices $1,4,5$ in order. Initially, the slime occupies $[1,2]$.

1. For $[1]$, the slime already occupies vertex $\mathbf{1}$, so $\mathrm{ans}_1=0$.
2. For $[1,4]$, one optimal process is $[\mathbf{1},2]\to[2,\underline{3}]\to[3,\underline{\mathbf{4}}]$, so $\mathrm{ans}_2=2$.
3. For $[1,4,5]$, one optimal process is $[\mathbf{1},2]\to[2,\underline{3}]\to[3,\underline{\mathbf{4}}]\to[3,\underline{\mathbf{5}}]$, so $\mathrm{ans}_3=3$.

In the second test case, after decoding, the food appears at vertices $5,3,6,2$ in order. Initially, the slime occupies $[1,2,3]$.

1. For $[5]$, one optimal process is $[1,2,3]\to[1,3,\underline{\mathbf{5}}]$, so $\mathrm{ans}_1=1$.
2. For $[5,3]$, the same process also lets the slime eat at vertex $\mathbf{3}$, so $\mathrm{ans}_2=1$.
3. For $[5,3,6]$, one optimal process is $[1,2,3]\to[1,3,\underline{\mathbf{5}}]\to[1,3,\underline{\mathbf{6}}]$, so $\mathrm{ans}_3=2$.
4. For $[5,3,6,2]$, one optimal process is $[1,2,3]\to[1,3,\underline{\mathbf{5}}]\to[1,3,\underline{\mathbf{6}}]\to[1,\underline{\mathbf{2}},3]$, so $\mathrm{ans}_4=3$.

In the third test case, after decoding, the food appears at vertices $7,5,6,4,3$ in order. Initially, the slime occupies $[1,2,4]$.

1. For $[7]$, one optimal process is $[1,2,4]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{7}}]$, so $\mathrm{ans}_1=2$.
2. For $[7,5]$, one optimal process is $[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}}]$, so $\mathrm{ans}_2=4$.
3. For $[7,5,6]$, one optimal process is $[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}}]\to[1,2,\underline{3}]\to[1,3,\underline{\mathbf{6}}]$, so $\mathrm{ans}_3=6$.
4. For $[7,5,6,4]$, continue with $[1,3,\mathbf{6}]\to[1,\underline{2},3]\to[1,2,\underline{\mathbf{4}}]$, so $\mathrm{ans}_4=8$.
5. For $[7,5,6,4,3]$, continue with $[1,2,\mathbf{4}]\to[1,2,\underline{\mathbf{3}}]$, so $\mathrm{ans}_5=9$.

In the fourth test case, after decoding, the food appears at vertices $3,4,5,2,1$.

In the fifth test case, after decoding, the food appears at vertices $6,1,3,5,2,4$.

In the sixth test case, after decoding, the food appears at vertices $7,5,6,1,4$.

在以下说明中，下划线标注的顶点表示一次“移动”（Move）后新占据的顶点，而黏液吃掉食物的顶点以粗体标出。

第一个测试用例中，解码后食物依次出现在顶点 $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]\to[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$。