P10289 [GESP样题 八级] 小杨的旅游
题目描述
小杨准备前往 B 国旅游。
B 国有 $n$ 座城市,这 $n$ 座城市依次以 $1$ 至 $n$ 编号。城市之间由 $n-1$ 条双向道路连接,任意两座城市之间均可达(即任意两座城市之间存在可达的路径)。
小杨可以通过双向道路在城市之间移动,通过一条双向道路需要 $1$ 单位时间。
B 国城市中有 $k$ 座城市设有传送门。设有传送门的城市的编号依次为 $b_1,b_2, \cdots ,b_k$。小杨可以从任意一座设有传送门的城市花费 $0$ 单位时间前往另一座设有传送门的城市。
注:如果两座设有传送门的城市之间存在双向道路,那么小杨可以选择通过双向道路移动,也可以选择通过传送门传送。
小杨计划在 B 国旅游 $q$ 次。第 $i$ 次旅游($1 \le i \le q$),⼩杨计划从编号为 $u_i$ 的城市前往编号为 $v_i$ 的城市,小杨希望你能求出所需要的最短时间。
输入格式
无
输出格式
无
说明/提示
| 子任务 | 分值 | $n \leq $ | $ k \leq $ | $q \leq $ |
|:-: | :-: | :-: | :-: | :-:|
| $1$ | $30$ | $500$ | $500$ | $1$ |
| $2$ | $30$ | $2 \times 10^5$ | $0$ | $2 \times 10^5$ |
| $3$ | $40$ | $2 \times 10^5$ | $2 \times 10^5$ | $2 \times 10^5$ |
对全部的测试数据,$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$。