← 返回题目列表

Codeforces · 1702/G2

G2. 可通行路径(硬版)

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

这是问题的困难版本。简单版本和困难版本之间的唯一区别在于查询数量。

Polycarp 从 $$$n$$$ 个顶点长出了一棵树。我们提醒您,$$$n$$$ 个顶点的树是由 $$$n$$$ 个顶点和 $$$n-1$$$ 个边组成的无向连通图,且不包含环。

如果树中存在这样一条路径,该路径经过该集合的每个顶点而不经过任何边两次,则他称一组顶点是可通过的。该路径可以访问其他顶点(不来自该集合)。

换句话说,如果存在一条简单路径穿过一组顶点(也可能是其他顶点)的所有顶点,则该组顶点称为可通过的。

例如,对于下面的树,设置 $$$\{3, 2, 5\}$$$, $$$\{1, 5, 4\}$$$, $$$\{1, 4\}$$$ 是可以的,$$$\{1, 3, 5\}$$$, $$$\{1, 2, 3, 4, 5\}$$$ 是不。

Polycarp 要求您回答 $$$q$$$ 问题。每个查询都是一组顶点。对于每个查询,都需要判断对应的顶点集是否可以通过。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 顶点数。

接下来的 $$$n - 1$$$ 行是树的描述。

每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — 由边连接的顶点的索引。

以下行包含单个整数 $$$q$$$ ($$$1 \le q \le 10^5$$$) — 查询数。

以下 $$$2 \cdot q$$$ 行包含集合的描述。

描述的第一行包含一个整数 $$$k$$$ ($$$1 \le k \le n$$$) — 集合的大小。

描述的第二行包含不同整数 $$$k$$$ $$$p_1, p_2, \dots, p_k$$$ ($$$1 \le p_i \le n$$$) — 集合顶点的索引。

保证所有查询的 $$$k$$$ 值的总和不超过 $$$2 \cdot 10^5$$$。

输出

输出 $$$q$$$ 行,每行都包含相应查询的答案。作为答案,如果集合通过,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

5
1 2
2 3
2 4
4 5
5
3
3 2 5
5
1 2 3 4 5
2
1 4
3
1 3 5
3
1 5 4

输出 #1

YES
NO
YES
NO
YES

输入 #2

5
1 2
3 2
2 4
5 2
4
2
3 1
3
3 4 5
3
2 3 5
1
1

输出 #2

YES
NO
YES
YES