We use rerooting DP to determine the winner for every possible initial root.
First, define two types of game states:
- $$$f(u,p)$$$: The current root is $$$u$$$, and the state is obtained by rerooting from $$$p$$$ to $$$u$$$. The direction toward $$$p$$$ is no longer available, and the current player has one extra Pass. The value is $$$1$$$ if the current player wins, and $$$0$$$ otherwise.
- $$$g(u)$$$: The current root is $$$u$$$, and no extra Pass is available. The value is $$$1$$$ if the current player wins, and $$$0$$$ otherwise.
If Bob chooses vertex $$$r$$$ as the initial root, Alice starts from state $$$g(r)$$$.
Our goal is to compute $$$g(u)$$$ for every vertex $$$u$$$ in $$$O(n)$$$ time.
1. DP Definitions
Choose vertex $$$1$$$ as an arbitrary temporary root.
For each vertex $$$u$$$, define
$$$ down[u] = f(u,parent(u)). $$$For each non-root vertex $$$u$$$, define
$$$ up[u] = f(parent(u),u). $$$Also, let
$$$ h(u) = \sum_{v \in child(u)} [down[v]=0]. $$$In other words, $$$h(u)$$$ is the number of children whose corresponding $$$f$$$-states are losing.
2. Computing down[u]
Let $$$c$$$ be the number of children of $$$u$$$.
In state $$$f(u,parent(u))$$$, the current player has one extra Pass.
There are two cases:
- If $$$h(u) \gt 0$$$, there exists a child $$$v$$$ such that $$$down[v]=0$$$. The current player can move the root to $$$v$$$ and leave a losing state to the opponent. Therefore, $$$down[u]=1$$$.
- Otherwise, all children have winning states. In this case, the result is determined by the parity of the number of available directions and the extra Pass. The current player wins exactly when $$$c$$$ is even.
Thus,
$$$ down[u]=1 \iff h(u) \gt 0 \lor c\bmod 2=0. $$$In particular, if $$$u$$$ is a leaf, then $$$c=0$$$, so $$$down[u]=1$$$.
We can compute all $$$down[u]$$$ and $$$h(u)$$$ using a bottom-up DFS.
3. Computing up[v]
Consider a child $$$v$$$ of vertex $$$u$$$. We need to compute
$$$ up[v]=f(u,v). $$$In this state, the current root is $$$u$$$, the extra Pass is available, and the direction toward $$$v$$$ is excluded.
The state is losing if and only if all of the following conditions hold:
- The parent direction does not lead to a losing state. This is automatically satisfied if $$$u$$$ is the temporary root. Otherwise, we require $$$up[u]=1$$$.
- None of the remaining children leads to a losing state. After excluding $$$v$$$, the number of losing child directions is $$$h(u)-[down[v]=0]$$$, which must be $$$0$$$.
- The number of remaining available directions is odd, since an $$$f$$$-state without a losing next state is losing exactly under this parity condition. There are $$$deg(u)-1$$$ remaining directions, so we require $$$deg(u)$$$ to be even.
Combining these conditions gives
$$$ \begin{aligned} up[v]=0 \iff {}& (parent(u)=0 \lor up[u]=1)\\ &\land (h(u)-[down[v]=0]=0)\\ &\land (deg(u)\bmod 2=0). \end{aligned} $$$Since $$$up[v]$$$ depends only on information already computed at $$$u$$$, we can calculate all $$$up$$$ values using a top-down DFS.
4. Computing g(u)
Now suppose $$$u$$$ is chosen as the initial root.
Unlike an $$$f$$$-state, the state $$$g(u)$$$ has no extra Pass, and all neighbors of $$$u$$$ are available.
The current player wins if at least one of the following conditions holds:
- Some child $$$v$$$ satisfies $$$down[v]=0$$$.
- The vertex $$$u$$$ has a parent, and $$$up[u]=0$$$.
- All neighboring directions lead to winning $$$f$$$-states, and $$$deg(u)$$$ is odd.
Therefore,
$$$ \begin{aligned} g(u)=1 \iff {}& h(u) \gt 0\\ &\lor (parent(u)\ne 0 \land up[u]=0)\\ &\lor (deg(u)\bmod 2=1). \end{aligned} $$$All the quantities required to evaluate $$$g(u)$$$ are now available.
5. Algorithm
- Root the tree at vertex $$$1$$$.
- Run a bottom-up DFS to compute $$$down[u]$$$ and $$$h(u)$$$ for every vertex.
- Run a top-down DFS to compute $$$up[u]$$$ for every non-root vertex.
- Evaluate $$$g(u)$$$ for every vertex using the derived formula.
- If there exists a vertex $$$r$$$ with $$$g(r)=0$$$, Bob can choose $$$r$$$ as the initial root and win. Otherwise, Alice wins regardless of Bob's choice.
6. Complexity Analysis
Each DFS visits every vertex and edge a constant number of times. Each DP transition takes $$$O(1)$$$ time after the required information has been computed.
Therefore, the total time complexity is $$$O(n)$$$.
The adjacency lists and DP arrays require $$$O(n)$$$ space, so the total space complexity is also $$$O(n)$$$.