{"problem":{"name":"[GESP样题 八级] 小杨的旅游","description":{"content":"小杨准备前往 B 国旅游。 B 国有 $n$ 座城市，这 $n$ 座城市依次以 $1$ 至 $n$ 编号。城市之间由 $n-1$ 条双向道路连接，任意两座城市之间均可达（即任意两座城市之间存在可达的路径）。 小杨可以通过双向道路在城市之间移动，通过一条双向道路需要 $1$ 单位时间。 B 国城市中有 $k$ 座城市设有传送门。设有传送门的城市的编号依次为 $b_1,b_2, \\cdots ,","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10289"},"statements":[{"statement_type":"Markdown","content":"小杨准备前往 B 国旅游。\n\nB 国有 $n$ 座城市，这 $n$ 座城市依次以 $1$ 至 $n$ 编号。城市之间由 $n-1$ 条双向道路连接，任意两座城市之间均可达（即任意两座城市之间存在可达的路径）。\n\n小杨可以通过双向道路在城市之间移动，通过一条双向道路需要 $1$ 单位时间。\n\nB 国城市中有 $k$ 座城市设有传送门。设有传送门的城市的编号依次为 $b_1,b_2, \\cdots ,b_k$。小杨可以从任意一座设有传送门的城市花费 $0$ 单位时间前往另一座设有传送门的城市。\n\n注：如果两座设有传送门的城市之间存在双向道路，那么小杨可以选择通过双向道路移动，也可以选择通过传送门传送。\n\n小杨计划在 B 国旅游 $q$ 次。第 $i$ 次旅游（$1 \\le i \\le q$），⼩杨计划从编号为 $u_i$ 的城市前往编号为 $v_i$ 的城市，小杨希望你能求出所需要的最短时间。\n\n## Input\n\n第一行包含三个正整数 $n,k,q$，分别表示 B 国的城市数量，设有传送门的城市数量，以及小杨计划在 B 国旅游的次数。  \n接下来 $n-1$ 行，每行包含两个正整数 $x_i, y_i$，表示一条双向道路连接的两座城市的编号。  \n第 $n + 1$ 行包含 $k$ 个正整数，表示设有传送门的城市的编号。  \n接下来 $q$ 行，每行包含两个正整数 $u_i,v_i$，表示小杨第 $i$ 次旅游行程的起点城市编号与终点城市编号。\n\n## Output\n\n输出共 $q$ 行。第 $i$ 行（$1 \\leq i \\leq q$）输出一个非负整数，表示小杨计划第 $i$ 次旅游从编号为 $u_i$ 的城市前往编号为 $v_i$ 的城市所需要的最短时间。\n\n[samples]\n\n## Background\n\n对应的选择、判断题：<https://ti.luogu.com.cn/problemset/1108>\n\n## Note\n\n| 子任务 | 分值 | $n \\leq $ | $ k \\leq $ | $q \\leq $ |\n|:-: | :-: | :-: | :-: | :-:|\n| $1$ | $30$ | $500$ | $500$ | $1$ |\n| $2$ | $30$ | $2 \\times 10^5$ | $0$ | $2 \\times 10^5$ |\n| $3$ | $40$ | $2 \\times 10^5$ | $2 \\times 10^5$ | $2 \\times 10^5$ |\n\n对全部的测试数据，$1 \\leq n \\leq 2 \\times 10^5$，$0 \\leq k \\leq n$，$1 \\leq x_i, y_i, u_i, v_i \\leq n$，$u_i \\neq v_i$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10289","tags":["广度优先搜索 BFS","最短路","最近公共祖先 LCA","GESP"],"sample_group":[["7 2 1\n5 7\n3 6\n2 3\n1 5\n5 4\n1 2\n7 4\n3 7\n","4"],["5 0 3\n2 3\n5 1\n5 2\n1 4\n4 5\n1 4\n4 3\n","2\n1\n4"]],"created_at":"2026-03-03 11:09:25"}}