B  Subtree Removal Game

We can perform a binary search for the solution. For a fixed value \(v\), let’s consider the following game:

\(Game(v)\): A leaf node holding an integer \(i \le v\) has label “F”, and holding \(i \gt v\) has label “S”. If a node with “F” remains at the end of the game, the first player (minimizer) wins. If “S” remains, the second (maximizer) wins.

If we determine the value such that the winner of \(Game(v)\) is the second player while that of \(Game(v+1)\) is the first player, we can conclude that the answer is \(v+1\). So, let’s consider solving \(Game(v)\) for some \(v\). Note that we only need to take labels “F” and “S” into account now. In what follows, we denote the two players as “F” and “S” for simplicity (“F” for the first and “S” for the second).

For a subtree rooted at node \(x\) and a player \(p\) (“F” or “S”), define \(Win(x, p)\) as the winner of a game that

• starts with player \(p\), and
• starts with subtree \(x\).

For a node \(x\), let’s define \(D(x)\) as follows:

• If \(x\) is a leaf node labeled “F”, \(D(x) = 1\).
• If \(x\) is a leaf node labeled “S”, \(D(x) = -1\).
• If \(x\) is a non-leaf, let \(S(x)\) is the sum of \(D(y)\) over its child nodes \(y\). Then, \(D(x)\) is the sign of \(S(x)\); that is, \(D(x) = 1\) if \(S(x) \gt 0\), \(D(x) = 0\) if \(S(x) = 0\), and \(D(x) = -1\) if \(S(x) \lt 0\).

We show the following argument by induction on the number of leaf nodes:

• If \(D(x) \gt 0\), \(Win(x, F) = Win(x, S) = F\),
• If \(D(x) = 0\), \(Win(x, F) = F\) and \(Win(x, S) = S\), and
• If \(D(x) \lt 0\), \(Win(x, F) = Win(x, S) = S\).

Without loss of generality, we can assume that the root node has at least 2 children, or the tree consists only of the root node. For the latter case, the argument is trivial. We consider the former case below.

When \(D(x) \gt 0\). If the root node \(x\) has at least one child \(y\) with \(D(y) \le 0\), the first player can choose \(y\). Otherwise, the first player can select any (immediate) child of \(x\). In either case, \(D(x) \gt 0\) holds after the operation.

When \(D(x) = 0\). We can find a path from \(x_0 = x\) to \(x_k\) where

• \(D(x_0) = ... = D(x_k) = 0\), and
• \(x_k\) has children \(y^+\) and \(y^-\) with \(D(y^+) \gt 0\) and \(D(y^-) \lt 0\).

Then, the first player can choose \(y^-\). After the operation \(D(x) \gt 0\) holds.

When \(D(x) \lt 0\). We note that the value of \(D\) changes by at most 1 after the operation. Therefore, \(D(x) \le 0\) holds after the operation.

From this argument, we can compute \(Win(x, F)\) by recursion in \(O(n)\). Overall time complexity is \(O(n \log n)\).