CF2237H Slime and Queries

给你一棵有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。有一种“史莱姆”正好占据树上的 $m$ 个顶点。保证被占据的顶点诱导子图是连通的。 最初，史莱姆占据顶点 $s_1,s_2,\ldots,s_m$。 我们先定义一个关于顶点序列的函数 $f$。考虑一个顶点序列 $a_1,a_2,\ldots,a_k$，有 $k$ 块食物，每一块第 $i$ 块食物放在顶点 $a_i$。一开始，只有第 $1$ 块食物出现。 史莱姆可以进行了如下操作，次数不限： - 移动。史莱姆从当前被占据的顶点中移出一个，并扩展到当前未被占据的顶点。形式上，设 $S$ 是当前被占据的顶点集，选择 $u\in S$ 和 $v\notin S$，并将 $S$ 替换为 $(S\setminus\{u\})\cup\{v\}$。操作后，$S$ 的诱导子图仍需连通。 - 吃。如果第 $i$ 块食物已经出现并且史莱姆当前占据顶点 $a_i$，那么史莱姆可以吃掉第 $i$ 块食物。若 $1\le i

每组测试包含多组数据。第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试组数。接下来是 $t$ 组数据。 每组数据第一行包含三个整数 $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$），表示已编码的询问顶点。 保证所有测试数据中 $\sum n\le 10^5$，$\sum q\le 10^5$。

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

下面的解释中，下划线的顶点是完成 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$。 由 ChatGPT 5 翻译