← 返回题目列表

AtCoder · arc148_c

C. 树上的灯灭了

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

分数: 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.