AT_arc148_c [ARC148C] Lights Out on Tree

[problemUrl]: https://atcoder.jp/contests/arc148/tasks/arc148_c 頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点の根付き木があります。頂点 $ 1 $ が根で、頂点 $ i $ $ (2\ \leq\ i\ \leq\ N) $ の親は頂点 $ P_i $ です。 表裏のあるコインが $ N $ 枚あります。コインは全ての頂点の上に $ 1 $ 枚ずつ載っています。 また、$ 1 $ から $ N $ までの番号がついた $ N $ 個のボタンがあります。ボタン $ n $ を押すと $ n $ を根とする部分木に含まれる頂点に載っている全てのコインが裏返ります。 以下で説明するクエリを $ Q $ 個処理してください。 $ i $ 番目のクエリではサイズ $ M_i $ の頂点集合 $ S_i\ =\ \lbrace\ v_{i,1},\ v_{i,2},\dots,\ v_{i,M_i}\ \rbrace $ が与えられます。 今、$ S_i $ に含まれる頂点の上に載っているコインは表を、それ以外のコインは裏を向いています。ボタンを $ 1 $ つ選んで押すことを繰り返して、$ N $ 枚のコイン全てを裏向きにするには、最小で何回ボタンを押す必要がありますか？答えを出力してください。ただし、どのようにボタンを押しても $ N $ 枚のコイン全てが裏向きにならない場合は $ -1 $ を出力してください。

N/A

N/A

### 制約 - $ 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} $ は互いに異なる - 入力される値はすべて整数 ### Sample Explanation 1 $ 1 $ 番目のクエリについて、以下に説明するようにボタンを $ 1 $ 回押すことで条件を満たすことができて、これが最小です。 - ボタン $ 1 $ を押す。頂点 $ 1,2,3,4,5,6 $ に載っているコインが裏返る。 $ 2 $ 番目のクエリについて、以下に説明するようにボタンを $ 2 $ 回押すことで条件を満たすことができて、これが最小です。 - ボタン $ 4 $ を押す。頂点 $ 4 $ に載っているコインが裏返る。 - ボタン $ 2 $ を押す。頂点 $ 2,4,5,6 $ に載っているコインが裏返る。