T546815 「2025 YAC Round 1」橙

「2025 YAC Round 1」F 题

幻想乡有 $n$ 个地点，地点编号从 $1$ 到 $n$。 这 $n$ 个地点之间由 $n - 1$ 条双向道路连接，任意两个地点互相可达。 橙 是八云家的一只可爱猫猫，她可以通过双向道路在幻想乡的各个地点移动。众所周知，猫猫的移动速度是比较快的，橙 **通过一条双向道路需要花费 $1$ 单位的时间。** 八云紫可以通过设置 隙间 来实现瞬间传送。 她想让 橙 更加方便且快速的移动，于是八云紫在 $n$ 个地点中的 $m$ 个地点设置了 隙间，地点编号依次为 $a_1, a_2, \ldots , a_m$。 任意两个设置 隙间 的地点可以互相瞬间传送，也就是说 橙 可以从任意一个设有 隙间 的地点花费 $0$ 单位的时间到达任意另外一个设有 隙间 的地点。 对于两个设有 隙间 的地点，橙 可以选择通过 隙间 进行瞬间传送，也可以选择通过双向道路进行移动。 现在，给定 $q$ 次询问。每次询问 橙 从编号为 $x$ 的地点到编号为 $y$ 的地点需要的 **最少时间**。

第一行输入三个整数 $n, m, q$（$1 \le n \le 2 \times 10^5, 0 \le m \le n, 1 \le q \le 2 \times 10^5$），分别表示 地点数、设置 隙间 的地点数 和 询问次数。 接下来 $n - 1$ 行，每行输入两个整数 $u, v$（$1 \le u, v \le n, u \not = v$），表示一条双向道路。 第 $n + 1$ 行，输入一行 $m$ 个整数 $a_1, a_2, \ldots, a_m$（$1 \le a_i \le n$），表示每个设置 隙间 的地点编号。 接下来 $q$ 行，每行输入两个每行输入两个整数 $x, y$（$1 \le x, y \le n$），分别表示询问的起点和终点的编号。

输出共 $q$ 行。 每一行输出一个整数表示答案。

#### 样例解释 对于样例 1，在编号为 $3$ 和 $4$ 的地点设置了隙间，可以互相瞬间传送。 对于 $1$ 到 $2$，直接走一步就可以到达。花费时间为 $1$； 对于 $3$ 到 $5$，由于 $3$ 设置了隙间，所以可以选择从 $3$ 先瞬间传送到 $4$，然后再按照 $4 \rightarrow 2 \rightarrow 5$ 的顺序走两步到达 $5$。花费时间为 $2$； 对于 $4$ 到 $3$，直接瞬间传送就可以了。花费时间为 $0$。