Cow and Vacation
题意翻译
**题目描述**
Bessie 正在准备度假。
他所在的个洲有 n 个城市,n-1 条双向道路连接。保证可以从任意一个城市到任意一个城市。
Bessie 考虑了 v 种度假方案,每种方案包括从城市 ai 开始到城市 bi 结束。
已知一共有 r 个城市拥有休息点。Bessie 容易疲倦,并且他不能在不休息的情况下穿越超过 k 条连续道路。有时,他还会因为太想休息而多次穿过同一个城市。
对于每一种旅行方案,Bessie 是否有从出发城市到结束地城市的旅行方式?
**输入格式**
第一行包括三个整数,n,k,r(范围如原题所示)。分别表示城市的数量,Bessie 愿意在不休息的情况下连续通过的最大道路数,休息点的数量。
接下来 n-1 行,每行两个整数写 xi 和 yi(范围如原题所示),表示从 xi 到 yi 有一条双向道路连接。
接下来r行,每行一个数字,表示有休息点的城市,保证每个城市最多出现一遍。
接下来一行一个整数 v(范围如原题所示),表示度假方案数。
接下来v行,每行两个整数 ai 和 bi(范围如原题所示),表示该方案从 ai 开始到城市 bi 结束。
**输出格式**
一共 v 行,表示如果 Bessie 能够按要求到达,输出“YES”,反之输出“NO”。
**说明/提示**
第一个例子的图表如下所示。休息站用红色表示。
对于第一个查询,Bessie 可以按以下顺序访问这些城市:1->2->3。
对于第二个查询,Bessie 可以按以下顺序访问这些城市: 3->2-> 4-> 5。
对于第三个查询,Bessie 无法前往目的地。例如,如果她试图这样旅行:3->2->4->5->6,他在2条以上的道路上旅行而没有休息。
题目描述
Bessie is planning a vacation! In Cow-lifornia, there are $ n $ cities, with $ n-1 $ bidirectional roads connecting them. It is guaranteed that one can reach any city from any other city.
Bessie is considering $ v $ possible vacation plans, with the $ i $ -th one consisting of a start city $ a_i $ and destination city $ b_i $ .
It is known that only $ r $ of the cities have rest stops. Bessie gets tired easily, and cannot travel across more than $ k $ consecutive roads without resting. In fact, she is so desperate to rest that she may travel through the same city multiple times in order to do so.
For each of the vacation plans, does there exist a way for Bessie to travel from the starting city to the destination city?
输入输出格式
输入格式
The first line contains three integers $ n $ , $ k $ , and $ r $ ( $ 2 \le n \le 2 \cdot 10^5 $ , $ 1 \le k,r \le n $ ) — the number of cities, the maximum number of roads Bessie is willing to travel through in a row without resting, and the number of rest stops.
Each of the following $ n-1 $ lines contain two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i, y_i \le n $ , $ x_i \neq y_i $ ), meaning city $ x_i $ and city $ y_i $ are connected by a road.
The next line contains $ r $ integers separated by spaces — the cities with rest stops. Each city will appear at most once.
The next line contains $ v $ ( $ 1 \le v \le 2 \cdot 10^5 $ ) — the number of vacation plans.
Each of the following $ v $ lines contain two integers $ a_i $ and $ b_i $ ( $ 1 \le a_i, b_i \le n $ , $ a_i \ne b_i $ ) — the start and end city of the vacation plan.
输出格式
If Bessie can reach her destination without traveling across more than $ k $ roads without resting for the $ i $ -th vacation plan, print YES. Otherwise, print NO.
输入输出样例
输入样例 #1
6 2 1
1 2
2 3
2 4
4 5
5 6
2
3
1 3
3 5
3 6
输出样例 #1
YES
YES
NO
输入样例 #2
8 3 3
1 2
2 3
3 4
4 5
4 6
6 7
7 8
2 5 8
2
7 1
8 1
输出样例 #2
YES
NO
说明
The graph for the first example is shown below. The rest stop is denoted by red.
For the first query, Bessie can visit these cities in order: $ 1, 2, 3 $ .
For the second query, Bessie can visit these cities in order: $ 3, 2, 4, 5 $ .
For the third query, Bessie cannot travel to her destination. For example, if she attempts to travel this way: $ 3, 2, 4, 5, 6 $ , she travels on more than $ 2 $ roads without resting.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1307F/6005795ec1e324d935b2c888363d240a51c05921.png)The graph for the second example is shown below.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1307F/366ba53d75a05a3319148dbe98d603e18b3769e5.png)