問題一覧 > 通常問題

No.2800 Game on Tree Inverse

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : noya2noya2 / テスター : 👑 potato167potato167 shobonvipshobonvip
3 ProblemId : 11014 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-06-28 21:04:01

問題文

頂点 $1,2,\dots ,N$ の $N$ 頂点からなる、頂点 $1$ を根とした根付き木が与えられます。 $i$ 番目の辺は頂点 $u_i,v_i$ を結んでいます。

Alice と Bob がこの木を使ってゲームを行います。はじめ、木の各頂点は白く塗られています。

ゲームは Alice から始めて次の操作を交互に行います。操作を行えなくなった方の負けで、そうでない方の勝ちです。

  • 白く塗られている頂点 $x$ を選び、 $x$ とその祖先となる頂点をすべて黒く塗り直す。

両者が自身の勝利を目指して最善を尽くしたときにどちらが勝つかを求めてください。

Alice が勝つ場合は、Alice が勝つために最初に選ぶ頂点 $x$ としてあり得るものをすべて求めてください。

制約

  • 入力はすべて整数
  • $2\le N\le 2\times 10^5$
  • $1\le u_i,v_i\le N\ (1\le i\le N-1)$
  • 与えられるグラフは木

入力

$N$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$

出力

Alice が勝つ場合は、Alice が勝つために最初に選ぶ頂点 $x$ としてあり得るものすべてを番号の昇順に並べた列を $x_1,x_2,\dots ,x_K$ とするとき、次の形式で出力してください。

Alice
$K$
$x_1$ $x_2$ $\dots x_K$

Bob が勝つ場合は Bob と出力してください。

Bob

サンプル

サンプル1
入力
3
1 2
1 3
出力
Alice
1
1

ゲームの展開の一例を示します。

  • Alice の手番からゲームが始まる。
  • この時点で白く塗られている頂点は $1,2,3$ である。Alice が頂点 $1$ を選ぶ。
  • この時点で白く塗られている頂点は $2,3$ である。Bob が頂点 $2$ を選ぶ。
  • この時点で白く塗られている頂点は $3$ である。Alice が頂点 $3$ を選ぶ。
  • この時点で白く塗られている頂点は存在しない。Alice の勝ちとなる。

サンプル2
入力
9
1 2
1 3
2 4
2 5
2 6
3 7
7 8
4 9
出力
Alice
2
5 6

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。