06593. GESP-8级-样题-小杨的旅游

题目描述

小杨准备前往 B 国旅游。

B 国有 $n$ 座城市，这 $n$ 座城市依次以 $1$ 至 $n$ 编号。城市之间由 $n - 1$ 条双向道路连接，任意两座城市之间均可达（即任意两座城市之间存在可达的路径）。

小杨可以通过双向道路在城市之间移动，通过一条双向道路需要 $1$ 单位时间。

B 国城市中有 $k$ 座城市设有传送门。设有传送门的城市的编号依次为 $b_{1}, b_{2}, \dots, b_{k}$ 。小杨可以从任意一座设有传送门的城市花费 $0$ 单位时间前往另一座设有传送门的城市。

注：如果两座设有传送门的城市之间存在双向道路，那么小杨可以选择通过双向道路移动，也可以选择通过传送门传送。

小杨计划在 B 国旅游 $q$ 次。第 $i$ 次旅游（ $1 \leq i \leq q$ ），小杨计划从编号为 $u_{i}$ 的城市前往编号为 $v_{i}$ 的城市，小杨希望你能求出所需要的最短时间。

输入格式

第一行包含三个正整数 $n, k, q$ ，分别表示 B 国的城市数量，设有传送门的城市数量，以及小杨计划在 B 国旅游的次数。
接下来 $n - 1$ 行，每行包含两个正整数 $x_{i}, y_{i}$ ，表示一条双向道路连接的两座城市的编号。
第 $n + 1$ 行包含 $k$ 个正整数，表示设有传送门的城市的编号。
接下来 $q$ 行，每行包含两个正整数 $u_{i}, v_{i}$ ，表示小杨第 $i$ 次旅游行程的起点城市编号与终点城市编号。

输出格式

输出共 $q$ 行。第 $i$ 行（ $1 \leq i \leq q$ ）输出一个非负整数，表示小杨计划第 $i$ 次旅游从编号为 $u_{i}$ 的城市前往编号为 $v_{i}$ 的城市所需要的最短时间。

样例

输入

输出

数据范围

子任务	分值	$n \leq$	$k \leq$	$q \leq$
$1$	$30$	$500$	$500$	$1$
$2$	$30$	$2 \times 1 0^{5}$	$0$	$2 \times 1 0^{5}$
$3$	$40$	$2 \times 1 0^{5}$	$2 \times 1 0^{5}$	$2 \times 1 0^{5}$

对全部的测试数据， $1 \leq n \leq 2 \times 1 0^{5}$ ， $0 \leq k \leq n$ ， $1 \leq x_{i}, y_{i}, u_{i}, v_{i} \leq n$ ， $u_{i} \neq = v_{i}$ 。

来源：洛谷 P10289（CCF GESP 8 级上机题）

06593. GESP-8级-样题-小杨的旅游 未做

题目描述

输入格式

输出格式

样例

数据范围

06593. GESP-8级-样题-小杨的旅游未做