No.2800 Game on Tree Inverse
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2