[1] Alice’s winning condition

The following proposition holds:

• Alice can win if and only if there is a vertex with \(f(v)=K\) in the initial state, or she can create a vertex with \(f(v)=K\) by choosing a vertex and writing a value on it.

The sufficiency is obvious. We will prove the necessity.

We need to show that, when Alice cannot win in one move, no matter what operation Alice performs, Bob can maintain a state where Alice cannot win in one move by performing an appropriate operation.

Suppose Alice writes a value on vertex \(u\). The vertices \(v\) whose \(f(v)\) is affected by this operation are limited to those that are in the path from vertex \(1\) to vertex \(u\) and yet to have \(f(v)\) determined (i.e., in the subtree rooted at \(v\), there is a vertex without a written value).

Among those vertices, let \(x\) be the deepest one. Bob can maintain a state where Alice cannot win in one move by choosing a vertex in the subtree of \(x\) without a written value and writing the value \(K\) on it.

This proves the proposition.

[2] How to check it

To determine the conditions of the proposition, we need to know the number of descendant vertices for each vertex and the number of vertices with each value written on them among the descendants. This can be done by performing a DFS for each vertex, which is fast enough in \(\mathrm{O}(N^2)\) or \(\mathrm{O}(N^2\log N)\).

Bonus: You can also solve this problem in \(\mathrm{O}(N\log^2 N)\) by bottom-up merging.

(Above is a modification of a translation by GPT-4.)