問題一覧 > 通常問題

No.2800 Game on Tree Inverse

レベル : / AI推定難易度 : 2525 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 11
作問者 : noya2 / テスター : 👑 potato167 shobonvip
お気に入りにしたユーザー ProblemId : 11014 / 自分の提出
問題文最終更新日: 2024-06-28 21:04:01
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 435 (順位表) の他の問題:

Problem Statement

You are given a rooted tree with $N$ vertices numbered $1,2,\dots ,N$, rooted at vertex $1$. The $i$-th edge connects vertices $u_i,v_i$.

Alice and Bob play a game using this tree. Initially, every vertex of the tree is painted white.

Starting with Alice, the players alternately perform the following operation. The player who cannot perform the operation loses, and the other player wins.

  • Choose a vertex $x$ painted white, and repaint $x$ and all of its ancestors black.

Determine who wins when both players play optimally to win.

If Alice wins, find all possible vertices $x$ that Alice can choose first in order to win.

Constraints

  • All input values are integers.
  • $2\le N\le 2\times 10^5$
  • $1\le u_i,v_i\le N\ (1\le i\le N-1)$
  • The given graph is a tree.

Input

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

Output

If Alice wins, let $x_1,x_2,\dots ,x_K$ be the sequence of all possible vertices $x$ that Alice can choose first in order to win, sorted in ascending order of vertex number, and output in the following format.

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

If Bob wins, output Bob.

Bob

Sample

Sample 1
Input
3
1 2
1 3
Output
Alice
1
1

Here is one example of how the game may proceed.

  • The game starts with Alice's turn.
  • At this point, the white vertices are $1,2,3$. Alice chooses vertex $1$.
  • At this point, the white vertices are $2,3$. Bob chooses vertex $2$.
  • At this point, the only white vertex is $3$. Alice chooses vertex $3$.
  • At this point, there are no white vertices. Alice wins.

Sample 2
Input
9
1 2
1 3
2 4
2 5
2 6
3 7
7 8
4 9
Output
Alice
2
5 6

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