分数: 500 点
问题陈述
我们有一棵有根树 N 顶点编号 1 to N。顶点 1 是根,也是顶点的父级 i 是顶点 P_i.
有 N 有正面和反面的硬币,每个顶点各一枚。
此外,还有 N 按钮编号 1 to N。按下按钮 n 翻转以顶点为根的子树中顶点上的所有硬币 n.
流程 Q 查询如下所述。
在 i-th 查询,给你一个大小的顶点集 M_i: S_i = \lbrace v_{i,1}, v_{i,2},\dots, v_{i,M_i} \rbrace.
现在,顶点上的硬币 S_i 正面朝上,其他正面朝上。为了让所有 N 反复选择一个按钮并按下,硬币正面朝上,至少需要按几次按钮?打印答案,或者 -1 如果没有办法让所有硬币都正面朝上。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq P_i \lt i
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq M_i
- \displaystyle \sum_{i=1}^Q M_i \leq 2 \times 10^5
- 1 \leq v_{i,j} \leq N
- v_{i,1}, v_{i,2},\dots,v_{i,M_i} 两两不同。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q
P_2 P_3 \dots P_N
M_1 v_{1,1} v_{1,2} \dots v_{1,M_1}
M_2 v_{2,1} v_{2,2} \dots v_{2,M_2}
\vdots
M_Q v_{Q,1} v_{Q,2} \dots v_{Q,M_Q}
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i-第一个查询。
示例输入 1
6 6 1 1 2 2 5 6 1 2 3 4 5 6 3 2 5 6 1 3 3 1 2 3 3 4 5 6 4 2 3 4 5
示例输出 1
1 2 1 3 2 3
对于第一个查询,只需按一下按钮即可满足要求,这是最少需要的,如下。
- 按下按钮 1,在顶点上翻转硬币 1,2,3,4,5,6.
对于第二个查询,按两次按钮即可满足要求,这是最少需要的,如下所示。
- 按下按钮 4,在顶点翻转硬币 4.
- 按下按钮 2,在顶点翻转硬币 2,4,5,6.