#P10289. [GESP样题 八级] 小杨的旅游

[GESP样题 八级] 小杨的旅游

题目描述

小杨准备前往 B 国旅游。

B 国有 nn 座城市,这 nn 座城市依次以 11nn 编号。城市之间由 n1n-1 条双向道路连接,任意两座城市之间均可达(即任意两座城市之间存在可达的路径)。

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

B 国城市中有 kk 座城市设有传送门。设有传送门的城市的编号依次为 b1,b2,,bkb_1,b_2, \cdots ,b_k。小杨可以从任意一座设有传送门的城市花费 00 单位时间前往另一座设有传送门的城市。

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

小杨计划在 B 国旅游 qq 次。第 ii 次旅游(1iq1 \le i \le q),⼩杨计划从编号为 uiu_i 的城市前往编号为 viv_i 的城市,小杨希望你能求出所需要的最短时间。

输入格式

第一行包含三个正整数 n,k,qn,k,q,分别表示 B 国的城市数量,设有传送门的城市数量,以及小杨计划在 B 国旅游的次数。
接下来 n1n-1 行,每行包含两个正整数 xi,yix_i, y_i,表示一条双向道路连接的两座城市的编号。
n+1n + 1 行包含 kk 个正整数,表示设有传送门的城市的编号。
接下来 qq 行,每行包含两个正整数 ui,viu_i,v_i,表示小杨第 ii 次旅游行程的起点城市编号与终点城市编号。

输出格式

输出共 qq 行。第 ii 行(1iq1 \leq i \leq q)输出一个非负整数,表示小杨计划第 ii 次旅游从编号为 uiu_i 的城市前往编号为 viv_i 的城市所需要的最短时间。

7 2 1
5 7
3 6
2 3
1 5
5 4
1 2
7 4
3 7

4
5 0 3
2 3
5 1
5 2
1 4
4 5
1 4
4 3

2
1
4

提示

子任务 分值 nn \leq k k \leq qq \leq
11 3030 500500 11
22 2×1052 \times 10^5 00 2×1052 \times 10^5
33 4040 2×1052 \times 10^5

对全部的测试数据,1n2×1051 \leq n \leq 2 \times 10^50kn0 \leq k \leq n1xi,yi,ui,vin1 \leq x_i, y_i, u_i, v_i \leq nxivix_i \neq v_i