All Falls Down

Define an integer $r(v)$ for each vertex $v$ as follows.

• If $v$ is a leaf, then $r(v)=0$.
• If a child $c$ with even $r(c)$ exists, take the minimum such value and add $1$.
• Otherwise, take the maximum $r(c)$ among all children and add $1$.

These values can be computed from the leaves upward. If $r(v)$ is positive and even, all children have odd values and their maximum is $r(v)-1$. If $r(v)$ is odd, there is an even-valued child with value $r(v)-1$, and every even-valued child has value at least .

When the tokens are at $u,v$, the player to move loses exactly when $\min(r(u),r(v))$ is even. Prove this by induction as both tokens move downward.

Suppose the minimum is an even value $k$. If $k=0$, one token has no legal move. If $k>0$, every child of a token with value $k$ has an odd value smaller than $k$. An even-valued child of the other token has value at least ; if that child is odd-valued instead, the minimum of the two child values is still odd. Thus every move reaches a position winning for the opponent.

Now suppose the minimum $k$ is odd. A token with value $k$ can move to an even-valued child with value $k-1$. If the other token has an odd value, it can move to an even-valued child with value at least $k-1$. If it has an even value, it can move to an odd-valued child with value at least $k$. Hence a move to a position with an even minimum always exists.

Bob moves first after Alice chooses a pair. Therefore we count pairs with an even minimum of their $r$ values. Count vertices by $r$ value and process these values in decreasing order. At an even value, add the pairs within its frequency group and the pairs between this group and all larger values. Store the answer in a $64$-bit integer.

The time and space complexity are both $O(N)$ per case.

Solution written by GPT6