No.2841 Leaf Eater
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 23
作問者 : milkcoffee / テスター : とりゐ 👑 ygussany
タグ : / 解いたユーザー数 23
作問者 : milkcoffee / テスター : とりゐ 👑 ygussany
問題文最終更新日: 2024-08-03 20:24:32
問題文
頂点に $1$ から $N$ の番号がついた $N$ 頂点の根付き木があります。頂点 $1$ はこの木の根であり、頂点 $i \ (2 \leq i)$ の親頂点は頂点 $p_i$ です。
これから先手と後手の $2$ 人のプレイヤーが交互に以下の操作を行います。
- 根付き木の 葉 である頂点を $1$ 個以上いくつか選ぶ。選んだ頂点とそれらに繋がる辺を全て削除する。
根付き木の葉とは、根以外の頂点のうち次数が $1$ の頂点のことを言います。
操作が行えなくなったプレイヤーの負けで、もう一方のプレイヤーの勝ちです。両者が自分の勝ちを目指すために最適に行動を行う場合、どちらのプレイヤーが勝つか判定してください。
$T$ 個のテストケースが与えられるので、それぞれについて答えて下さい。
入力
$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$ただし、 $case_i$ は $i$ 番目のテストケースを表す。
各テストケースは以下の形式で与えられる。
$N$ $p_2$ $p_3$ $\ldots$ $p_N$
- $1 \leq T \leq 10^5$
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq p_i < i \ (2 \leq i \leq N)$
- 入力はすべて整数
- $1$ つの入力に含まれるテストケースについて、$N$ の総和は $2 \times 10^5$ 以下
出力
先手が勝つならば First
を、後手が勝つならば Second
を出力してください。
$i$ 番目のテストケースに対する答えを $i$ 行目に出力してください。
サンプル
サンプル1
入力
3 4 1 1 1 3 1 2 7 1 1 2 2 3 3
出力
First Second First
$1$ つ目のテストケースについて、まず先手が頂点 $2,3,4$ を削除したとします。
最後に残った頂点 $1$ は削除できないため、後手は操作が行えません。よって後手の負けとなり、先手が勝ちとなります。
$2$ つ目のテストケースについて、先手は頂点 $3$ を削除するしかありません。
次に後手が頂点 $2$ を削除します。その次に先手は操作が行えないため、後手が勝ちとなります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。