Codeforces Round 621 (Div. 1 + Div. 2)
F
Cow and Vacation
Codeforces
3300
原题
← EG →
翻译中…

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?

翻译中…

Input

翻译中…

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.

翻译中…

Output

翻译中…

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.

翻译中…

Note

翻译中…

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.

翻译中…

image

翻译中…

The graph for the second example is shown below.

翻译中…

image

翻译中…

样例

Input #1
6 2 1
1 2
2 3
2 4
4 5
5 6
2
3
1 3
3 5
3 6
Output #1
YES
YES
NO
InputCopy OutputCopy
Input #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
Output #2
YES
NO
InputCopy OutputCopy
题目信息
题号
1307F
时间限制
2 s
内存限制
256 MB
标签
DFS 及类似
并查集
树

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。