← 返回题目列表

Codeforces · 1328/E

E. 树查询

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

给你一个有根树,由 $$$n$$$ 顶点组成,编号从 $$$1$$$ 到 $$$n$$$。树的根是顶点号$$$1$$$。

树是具有 $$$n-1$$$ 边的连通无向图。

您收到了 $$$m$$$ 查询。第 $$$i$$$ 查询由一组 $$$k_i$$$ 不同顶点 $$$v_i[1]、v_i[2]、\dots、v_i[k_i]$$$ 组成。你的任务是判断是否存在从根到某个顶点 $$$u$$$ 的路径,使得每个给定的 $$$k$$$ 顶点要么属于该路径,要么到该路径的某个顶点的距离为 $$$1$$$。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) — 树中的顶点数和查询数。

接下来的 $$$n-1$$$ 行描述了树的一条边。边 $$$i$$$ 由两个整数 $$$u_i$$$ 和 $$$v_i$$$ 表示,它连接的顶点的标签 $$$(1 \le u_i, v_i \le n, u_i \ne v_i$$$)。

保证给定的边形成一棵树。

接下来的 $$$m$$$ 行描述查询。第 $$$i$$$ 行描述第 $$$i$$$ 查询,并以整数 $$$k_i$$$ ($$$1 \le k_i \le n$$$) 开头 — 当前查询中的顶点数。然后 $$$k_i$$$ 整数如下:$$$v_i[1], v_i[2], \dots, v_i[k_i]$$$ ($$$1 \le v_i[j] \le n$$$),其中 $$$v_i[j]$$$ 是第 $$$i$$$ 个查询的第 $$$j$$$ 个顶点。

保证单个查询中的所有顶点都是不同的。

保证 $$$k_i$$$ 之和不超过 $$$2 \cdot 10^5$$$ ($$$\sum\limits_{i=1}^{m} k_i \le 2 \cdot 10^5$$$)。

输出

对于每个查询,打印答案 —“是”,如果存在从根到某个顶点 $$$u$$$ 的路径,使得每个给定的 $$$k$$$ 顶点要么属于该路径,要么到该路径的某个顶点的距离为 $$$1$$$,否则为“否”。

示例

输入 #1

10 6
1 2
1 3
1 4
2 5
2 6
3 7
7 8
7 9
9 10
4 3 8 9 10
3 2 4 6
3 2 1 5
3 4 8 2
2 6 10
3 5 4 7

输出 #1

YES
YES
YES
YES
NO
NO

注意

示例对应的图片:

考虑查询。

第一个查询是 $$$[3, 8, 9, 10]$$$。答案是“是”,因为您可以选择从根 $$$1$$$ 到顶点 $$$u=10$$$ 的路径。那么顶点 $$$[3, 9, 10]$$$ 属于从 $$$1$$$ 到 $$$10$$$ 的路径,顶点 $$$8$$$ 到也属于该路径的顶点 $$$7$$$ 的距离为 $$$1$$$。

第二个查询是 $$$[2, 4, 6]$$$。答案是“是”,因为您可以选择到达顶点 $$$u=2$$$ 的路径。那么顶点 $$$4$$$ 到属于该路径的顶点 $$$1$$$ 的距离为 $$$1$$$,而顶点 $$$6$$$ 到属于该路径的顶点 $$$2$$$ 的距离为 $$$1$$$。

第三个查询是 $$$[2, 1, 5]$$$。答案是“是”,因为您可以选择到顶点 $$$u=5$$$ 的路径,并且查询的所有顶点都属于该路径。

第四个查询是 $$$[4, 8, 2]$$$。答案是“是”,因为您可以选择到顶点 $$$u=9$$$ 的路径,因此顶点 $$$2$$$ 和 $$$4$$$ 到属于该路径的顶点 $$$1$$$ 的距离均为 $$$1$$$,而顶点 $$$8$$$ 到属于该路径的顶点 $$$7$$$ 的距离为 $$$1$$$。

第五个和第六个查询的答案都是“否”,因为您无法选择合适的顶点$$$u$$$。