← 返回题目列表

Codeforces · 1307/F

F. 牛和假期

中文机器翻译题面 查看原题

贝西正在计划度假!在 Cow-lifornia,有 $$$n$$$ 个城市,有 $$$n-1$$$ 双向道路连接它们。保证可以从任意一个城市到达任意一个城市。

Bessie 正在考虑 $$$v$$$ 可能的假期计划,第 $$$i$$$ 个假期计划由出发城市 $$$a_i$$$ 和目的地城市 $$$b_i$$$ 组成。

据了解,只有 $$$r$$$ 的城市有休息站。 Bessie 很容易疲劳,而且在不休息的情况下无法连续行驶超过 $$$k$$$ 条道路。事实上,她非常渴望休息,因此可能会多次穿越同一个城市。

对于每个假期计划,Bessie 是否存在从出发城市到目的地城市的方式?

输入

第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$r$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le k,r \le n$$$) — 城市数量、Bessie 愿意在不休息的情况下连续行驶的最大道路条数以及休息站的数量。

以下 $$$n-1$$$ 行中的每一行都包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$, $$$x_i \neq y_i$$$),表示城市 $$$x_i$$$ 和城市 $$$y_i$$$ 通过道路连接。

下一行包含由空格分隔的 $$$r$$$ 整数 - 有休息站的城市。每个城市最多出现一次。

下一行包含 $$$v$$$ ($$$1 \le v \le 2 \cdot 10^5$$$) — 假期计划的数量。

以下 $$$v$$$ 行均包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$) — 假期计划的开始和结束城市。

输出

如果 Bessie 无需穿越超过 $$$k$$$ 条道路且无需在第 $$$i$$$ 个假期计划中休息即可到达目的地,则打印 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

注意

第一个示例的图表如下所示。休息站用红色表示。

对于第一个查询,Bessie 可以按顺序访问这些城市:$$$1, 2, 3$$$。

对于第二个查询,Bessie 可以按顺序访问这些城市:$$$3, 2, 4, 5$$$。

对于第三个查询,Bessie 无法前往目的地。例如,如果她尝试这样行驶:$$$3, 2, 4, 5, 6$$$,则她会在超过 $$$2$$$ 的道路上行驶而不休息。

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