Subtree Removal Game

Research check: the intended route is the binary-search plus signed tree game from the official tutorial PDF, cross-checked against the Codeforces statement and status page showing accepted C++ submissions for B. Sources: statement, official tutorial PDF, status. No submission code is copied.

Threshold Game

Instead of trying to directly minimize/maximize the final label, fix a candidate value $x$.

Color each original leaf:

• $F$ if its label $i \le x$.
• $S$ if its label $i > x$.

Now the minimizer wants an $F$ leaf to remain, while the maximizer wants an $S$ leaf to remain. If we can decide whether the first player wins this threshold game, then the real answer is the smallest winning $x$.

Important: only original leaves have written numbers. If an internal node becomes a leaf later, it does not suddenly get a label. Sneaking that assumption in is a great way to produce very confident garbage.

The Bottom-Up Value

For a fixed $x$, define $D_x(u)$:

• If $u$ is an original leaf and $u \le x$, then $D_x(u)=1$.
• If $u$ is an original leaf and $u>x$, then $D_x(u)=-1$.
• Otherwise, let $s=\sum D_x(c)$ over children $c$ of $u$. Then $D_x(u)=1$ if $s>0$, $D_x(u)=0$ if $s=0$, and $D_x(u)=-1$ if $s<0$.

So every subtree is summarized by one of three states.

Meaning Of The Sign

For the threshold game inside a subtree rooted at $u$:

• $D_x(u)=1$: player $F$ can force an $F$ survivor no matter whose turn it is.
• $D_x(u)=-1$: player $S$ can force an $S$ survivor no matter whose turn it is.
• $D_x(u)=0$: the player to move can force their own color.

Here is the proof idea.

A single move removes one subtree, so it only changes values along one ancestor path. At every ancestor, the child contribution changes by at most $1$ in the ordered set $-1,0,1$, so the ancestor's sign also cannot jump from $1$ straight to $-1$ or from $-1$ straight to $1$.

If $D_x(u)=0$, there is a path through zero-valued nodes until we reach a zero-valued node with both a positive child and a negative child. Why must this exist? A labeled leaf is never zero, so if a zero node with written leaves does not already have mixed signs, we keep descending into a zero child that still contains written leaves. Then:

• $F$ removes a negative child, making that node positive, and this positivity propagates back up to $u$.
• $S$ removes a positive child, symmetrically making the root negative.

Thus a zero state is a first-player win for the threshold game.

If $D_x(u)=1$, the $F$ player can keep the position nonnegative when moving: remove a non-positive child if one exists; otherwise all meaningful children are positive, and removing one still does not give $S$ a decisive negative state. If $S$ moves from $D_x(u)=1$, the one-move-change lemma says the result is still $1$ or $0$, and then $F$ wins from there. The $D_x(u)=-1$ case is perfectly symmetric.

For the real game, the minimizer moves first, so threshold $x$ is winnable exactly when:

$D_x(1) \ge 0.$

Binary Search

As $x$ increases, some leaves switch from $-1$ to $1$, never the other way around. Since every internal value is just the sign of a sum of monotone child values, $D_x(1)$ is monotone too. Therefore the predicate $D_x(1) \ge 0$ is monotone, and we binary search the smallest valid $x$.

Because parents satisfy $p_i<i$, every child has a larger index than its parent. That means one reverse loop from $n$ down to $1$ computes all $D_x(u)$ values. No DFS stack, no recursion-depth drama.

Edge cases:

• A tree with one original leaf works automatically: the root value switches only at that leaf's label.
• Degree-one chains just pass the sign upward.
• If $x$ is a non-leaf index, no leaf changes color, so the binary search still lands on an actual leaf label.

Each check is $O(n)$, and binary search does $O(\log n)$ checks. Total complexity is $O(n\log n)$ time and $O(n)$ memory.