CF1307F.Cow and Vacation
NOI/NOI+/CTSC
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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 ai and destination city bi.
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?
贝茜正在计划一次假期!在牛加利福尼亚州(Cow-lifornia),共有 n 座城市,由 n−1 条双向道路连接。保证任意两座城市之间均可互相到达。
贝茜正在考虑 v 种可能的度假方案,其中第 i 种方案指定起点城市为 ai、终点城市为 bi。
已知仅有 r 座城市设有休息站。贝茜很容易疲劳,若不休息,则她无法连续经过超过 k 条道路。事实上,她对休息如此渴望,以至于可能会多次经过同一座城市以确保能及时休息。
对于每一种度假方案,是否存在一条从起点城市到终点城市的可行路径?
输入格式
The first line contains three integers n, k, and r (2≤n≤2⋅105, 1≤k,r≤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 xi and yi (1≤xi,yi≤n, xi=yi), meaning city xi and city yi 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≤v≤2⋅105) — the number of vacation plans.
Each of the following v lines contain two integers ai and bi (1≤ai,bi≤n, ai=bi) — the start and end city of the vacation plan.
第一行包含三个整数 n、k 和 r(2≤n≤2⋅105,1≤k,r≤n)——分别表示城市的数量、Bessie 愿意连续经过的道路的最大条数(途中不休息),以及休息站的数量。
接下来的 n−1 行,每行包含两个整数 xi 和 yi(1≤xi,yi≤n,xi=yi),表示城市 xi 与城市 yi 之间有一条道路相连。
下一行包含 r 个由空格分隔的整数——这些是设有休息站的城市编号。每个城市至多出现一次。
再下一行包含一个整数 v(1≤v≤2⋅105)——表示度假计划的数量。
接下来的 v 行,每行包含两个整数 ai 和 bi(1≤ai,bi≤n,ai=bi)——分别表示第 i 个度假计划的起点城市和终点城市。
输出格式
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.
如果贝茜能够到达目的地,且在第 i 个度假计划中,不休息地连续经过的道路数不超过 k 条,则输出 YES;否则输出 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.

The graph for the second example is shown below.

第一个样例的图示如下所示,休息站用红色标出。
对于第一个查询,贝茜可以按以下顺序访问这些城市:1,2,3。
对于第二个查询,贝茜可以按以下顺序访问这些城市:3,2,4,5。
对于第三个查询,贝茜无法到达目的地。例如,若她尝试按 3,2,4,5,6 的路径行进,则会在未休息的情况下经过超过 2 条道路。

第二个样例的图示如下所示。

输入解题思路,AI测评打分。不知道怎么写?