#1489. CF1328E Tree Queries

CF1328E Tree Queries

【题目描述】

给定一棵以 11 号结点为根的有根树,树上共有 nn 个结点,编号为 11nn

现在有 mm 个询问。每个询问给出 kik_i 个互不相同的结点 vi[1],vi[2],,vi[ki]v_i[1],v_i[2],\dots,v_i[k_i]

你需要判断是否存在某个结点 uu,使得从根结点 11 到结点 uu 的路径满足:对于询问给出的每个结点,它要么在这条路径上,要么与这条路径上的某个结点距离恰好为 11

【输入格式】

第一行输入两个整数 n,mn,m,表示树的结点数和询问数。

接下来 n1n-1 行,每行两个整数 ui,viu_i,v_i,表示树上的一条无向边。输入保证这些边构成一棵树,根为 11

接下来 mm 行,每行描述一个询问。每行先输入一个整数 kik_i,表示当前询问的结点数量;随后输入 kik_i 个互不相同的整数,表示这些结点编号。

【输出格式】

对于每个询问,如果存在满足条件的从根到某个结点的路径,输出 YES,否则输出 NO

【样例输入】

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

【样例输出】

YES
YES
YES
YES
NO
NO

【提示】

数据范围:2n2×1052 \le n \le 2\times 10^51m2×1051 \le m \le 2\times 10^5,所有询问中 kik_i 的总和不超过 2×1052\times 10^5