CF1702G2.Passable Paths (hard version)

This is a hard version of the problem. The only difference between an easy and a hard version is in the number of queries.

Polycarp grew a tree from $n$ vertices. We remind you that a tree of $n$ vertices is an undirected connected graph of $n$ vertices and $n-1$ edges that does not contain cycles.

He calls a set of vertices passable if there is such a path in the tree that passes through each vertex of this set without passing through any edge twice. The path can visit other vertices (not from this set).

In other words, a set of vertices is called passable if there is a simple path that passes through all the vertices of this set (and possibly some other).

For example, for a tree below sets ${3, 2, 5}$, ${1, 5, 4}$, ${1, 4}$ are passable, and ${1, 3, 5}$, ${1, 2, 3, 4, 5}$ are not.

Polycarp asks you to answer $q$ queries. Each query is a set of vertices. For each query, you need to determine whether the corresponding set of vertices is passable.

这是一个该问题的困难版本。简单版本与困难版本的唯一区别在于查询次数。

波利卡普构造了一棵包含 $n$ 个顶点的树。我们提醒您：一棵含 $n$ 个顶点的树，是指一个具有 $n$ 个顶点、$n-1$ 条边、无环且连通的无向图。

他将一个顶点集合称为可通行的（passable），如果树中存在一条路径，该路径经过该集合中的每个顶点，且不重复经过任何一条边（但允许经过集合外的其他顶点）。

换言之，一个顶点集合被称为可通行的，当且仅当存在一条简单路径，它经过该集合的所有顶点（也可能经过一些额外顶点）。

例如，对于下图所示的树，集合 $\{3, 2, 5\}$、$\{1, 5, 4\}$、$\{1, 4\}$ 是可通行的，而 $\{1, 3, 5\}$、$\{1, 2, 3, 4, 5\}$ 则不是。

波利卡普要求你回答 $q$ 个查询。每个查询给出一个顶点集合。对每个查询，你需要判断对应的顶点集合是否可通行。

The first line of input contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — number of vertices.

Following $n - 1$ lines a description of the tree..

Each line contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$) — indices of vertices connected by an edge.

Following line contains single integer $q$ ($1 \le q \le 10^5$) — number of queries.

The following $2 \cdot q$ lines contain descriptions of sets.

The first line of the description contains an integer $k$ ($1 \le k \le n$) — the size of the set.

The second line of the description contains $k$ of distinct integers $p_1, p_2, \dots, p_k$ ($1 \le p_i \le n$) — indices of the vertices of the set.

It is guaranteed that the sum of $k$ values for all queries does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $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$。

Output $q$ lines, each of which contains the answer to the corresponding query. As an answer, output "YES" if the set is passable, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).

输出 $q$ 行，每行包含对应查询的答案。若该集合是可通行的，则输出 "YES"；否则输出 "NO"。

答案大小写不敏感（例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均被视为肯定回答）。