309584: CF1702G1. Passable Paths (easy version)
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Passable Paths (easy version)
题意翻译
### 题目描述 给定一棵树，问是否能通过一条简单路径（即在树上找一条路径且不重复走一条边），使其经过给定点集中的所有点。 ### 输入格式 第一行，一个数 $n$，表示点数。 以下 $n-1$ 行，每行两个数 $u,v$，表示点 $u$ 和点 $v$ 之间有一条边。 接下来是一个数 $q$，表示询问的组数。 对于每组询问： + 第一行有一个数 $k$，表示点集的大小。 + 第二行有 $k$个数 $p_1,p_2,...,p_k$，表示这个点集。 ### 输出格式 输出共 $q$ 行。 对于每个询问，输出一行 `YES` 或者 `NO` 表示答案，大小写不敏感。 ### 数据范围 对于 $100\%$ 的数据： + $1 \le n \le 2 \cdot 10^5$，$ 1 \le u, v \le n$，$ u \ne v$； + $ 1 \le q \le 5$，$ 1 \le k \le n$，$ 1 \le p_i \le n$，所有 $k$ 的和不超过 $2\cdot10^5$。题目描述
This is an easy 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.输入输出格式
输入格式
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 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 $ .
输出格式
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).
输入输出样例
输入样例 #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
YESInput
题意翻译
### 题目描述 给定一棵树，问是否能通过一条简单路径（即在树上找一条路径且不重复走一条边），使其经过给定点集中的所有点。 ### 输入格式 第一行，一个数 $n$，表示点数。 以下 $n-1$ 行，每行两个数 $u,v$，表示点 $u$ 和点 $v$ 之间有一条边。 接下来是一个数 $q$，表示询问的组数。 对于每组询问： + 第一行有一个数 $k$，表示点集的大小。 + 第二行有 $k$个数 $p_1,p_2,...,p_k$，表示这个点集。 ### 输出格式 输出共 $q$ 行。 对于每个询问，输出一行 `YES` 或者 `NO` 表示答案，大小写不敏感。 ### 数据范围 对于 $100\%$ 的数据： + $1 \le n \le 2 \cdot 10^5$，$ 1 \le u, v \le n$，$ u \ne v$； + $ 1 \le q \le 5$，$ 1 \le k \le n$，$ 1 \le p_i \le n$，所有 $k$ 的和不超过 $2\cdot10^5$。Output
**题目大意**：
给定一棵树，需要判断是否存在一条简单路径（不重复经过任何边），可以经过某个点集中的所有点。
**输入数据格式**：
- 第一行：一个整数 $ n $，表示点的数量。
- 接下来的 $ n-1 $ 行：每行两个整数 $ u, v $，表示点 $ u $ 和点 $ v $ 之间有一条边。
- 接下来一行：一个整数 $ q $，表示询问的组数。
- 每组询问：
- 第一行：一个整数 $ k $，表示点集的大小。
- 第二行：$ k $ 个整数 $ p_1, p_2, \ldots, p_k $，表示这个点集。
**输出数据格式**：
- 输出共 $ q $ 行。
- 对于每个询问，输出一行 `YES` 或者 `NO` 表示答案，大小写不敏感。
**数据范围**：
- 对于 $100\%$ 的数据：
- $1 \le n \le 2 \cdot 10^5$，$ 1 \le u, v \le n$，$ u \ne v$；
- $ 1 \le q \le 5$，$ 1 \le k \le n$，$ 1 \le p_i \le n$，所有 $ k $ 的和不超过 $2 \cdot 10^5$。
**题目描述（英文）**：
This is an easy 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 $（$ 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 5 $）——查询数。
- 接下来的 $ 2 \cdot q $ 行：包含集合的描述。
- 描述的第一行：一个整数 $ k $（$ 1 \le k \le n $）——集合的大小。
- 描述的第二行：$ k $ 个不同的整数 $ p_1, p_2, \ldots, p_k $（$ 1 \le p_i \le n $）——集合中顶点的索引。
- 保证所有查询的 $ k $ 值之和不超过 $ 2 \cdot 10^5 $。
**输出格式**：
- 输出 $ q $ 行，每行包含对应查询的答案。如果集合是可通行的，则输出“YES”，否则输出“NO”。
- 可以在任何情况下输出答案（例如，字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案）。**题目大意**： 给定一棵树，需要判断是否存在一条简单路径（不重复经过任何边），可以经过某个点集中的所有点。 **输入数据格式**： - 第一行：一个整数 $ n $，表示点的数量。 - 接下来的 $ n-1 $ 行：每行两个整数 $ u, v $，表示点 $ u $ 和点 $ v $ 之间有一条边。 - 接下来一行：一个整数 $ q $，表示询问的组数。 - 每组询问： - 第一行：一个整数 $ k $，表示点集的大小。 - 第二行：$ k $ 个整数 $ p_1, p_2, \ldots, p_k $，表示这个点集。 **输出数据格式**： - 输出共 $ q $ 行。 - 对于每个询问，输出一行 `YES` 或者 `NO` 表示答案，大小写不敏感。 **数据范围**： - 对于 $100\%$ 的数据： - $1 \le n \le 2 \cdot 10^5$，$ 1 \le u, v \le n$，$ u \ne v$； - $ 1 \le q \le 5$，$ 1 \le k \le n$，$ 1 \le p_i \le n$，所有 $ k $ 的和不超过 $2 \cdot 10^5$。 **题目描述（英文）**： This is an easy 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 $（$ 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 5 $）——查询数。 - 接下来的 $ 2 \cdot q $ 行：包含集合的描述。 - 描述的第一行：一个整数 $ k $（$ 1 \le k \le n $）——集合的大小。 - 描述的第二行：$ k $ 个不同的整数 $ p_1, p_2, \ldots, p_k $（$ 1 \le p_i \le n $）——集合中顶点的索引。 - 保证所有查询的 $ k $ 值之和不超过 $ 2 \cdot 10^5 $。 **输出格式**： - 输出 $ q $ 行，每行包含对应查询的答案。如果集合是可通行的，则输出“YES”，否则输出“NO”。 - 可以在任何情况下输出答案（例如，字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案）。
给定一棵树，需要判断是否存在一条简单路径（不重复经过任何边），可以经过某个点集中的所有点。
**输入数据格式**：
- 第一行：一个整数 $ n $，表示点的数量。
- 接下来的 $ n-1 $ 行：每行两个整数 $ u, v $，表示点 $ u $ 和点 $ v $ 之间有一条边。
- 接下来一行：一个整数 $ q $，表示询问的组数。
- 每组询问：
- 第一行：一个整数 $ k $，表示点集的大小。
- 第二行：$ k $ 个整数 $ p_1, p_2, \ldots, p_k $，表示这个点集。
**输出数据格式**：
- 输出共 $ q $ 行。
- 对于每个询问，输出一行 `YES` 或者 `NO` 表示答案，大小写不敏感。
**数据范围**：
- 对于 $100\%$ 的数据：
- $1 \le n \le 2 \cdot 10^5$，$ 1 \le u, v \le n$，$ u \ne v$；
- $ 1 \le q \le 5$，$ 1 \le k \le n$，$ 1 \le p_i \le n$，所有 $ k $ 的和不超过 $2 \cdot 10^5$。
**题目描述（英文）**：
This is an easy 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 $（$ 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 5 $）——查询数。
- 接下来的 $ 2 \cdot q $ 行：包含集合的描述。
- 描述的第一行：一个整数 $ k $（$ 1 \le k \le n $）——集合的大小。
- 描述的第二行：$ k $ 个不同的整数 $ p_1, p_2, \ldots, p_k $（$ 1 \le p_i \le n $）——集合中顶点的索引。
- 保证所有查询的 $ k $ 值之和不超过 $ 2 \cdot 10^5 $。
**输出格式**：
- 输出 $ q $ 行，每行包含对应查询的答案。如果集合是可通行的，则输出“YES”，否则输出“NO”。
- 可以在任何情况下输出答案（例如，字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案）。**题目大意**： 给定一棵树，需要判断是否存在一条简单路径（不重复经过任何边），可以经过某个点集中的所有点。 **输入数据格式**： - 第一行：一个整数 $ n $，表示点的数量。 - 接下来的 $ n-1 $ 行：每行两个整数 $ u, v $，表示点 $ u $ 和点 $ v $ 之间有一条边。 - 接下来一行：一个整数 $ q $，表示询问的组数。 - 每组询问： - 第一行：一个整数 $ k $，表示点集的大小。 - 第二行：$ k $ 个整数 $ p_1, p_2, \ldots, p_k $，表示这个点集。 **输出数据格式**： - 输出共 $ q $ 行。 - 对于每个询问，输出一行 `YES` 或者 `NO` 表示答案，大小写不敏感。 **数据范围**： - 对于 $100\%$ 的数据： - $1 \le n \le 2 \cdot 10^5$，$ 1 \le u, v \le n$，$ u \ne v$； - $ 1 \le q \le 5$，$ 1 \le k \le n$，$ 1 \le p_i \le n$，所有 $ k $ 的和不超过 $2 \cdot 10^5$。 **题目描述（英文）**： This is an easy 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 $（$ 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 5 $）——查询数。 - 接下来的 $ 2 \cdot q $ 行：包含集合的描述。 - 描述的第一行：一个整数 $ k $（$ 1 \le k \le n $）——集合的大小。 - 描述的第二行：$ k $ 个不同的整数 $ p_1, p_2, \ldots, p_k $（$ 1 \le p_i \le n $）——集合中顶点的索引。 - 保证所有查询的 $ k $ 值之和不超过 $ 2 \cdot 10^5 $。 **输出格式**： - 输出 $ q $ 行，每行包含对应查询的答案。如果集合是可通行的，则输出“YES”，否则输出“NO”。 - 可以在任何情况下输出答案（例如，字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案）。