[1] Alice の勝利条件

以下の命題が成り立ちます。

• Alice が勝利できることは、初期状態で \(f(v)=K\) なる頂点が存在するか、頂点を一つ選んで値を書き込むことで、\(f(v)=K\) なる頂点を作り出せることと同値である。

十分性は明らかです。必要性を証明します。

Alice が一手で勝利できない状態のとき、Alice がどんな操作を行っても、Bob が適切な操作を行うことで Alice が一手で勝利できない状態を保てることを示せばよいです。

Alice が頂点 \(u\) に値を書き込んだとします。この操作によって \(f(v)\) が影響を受けるような頂点 \(v\) は、頂点 \(1\) から頂点 \(u\) へのパスに含まれ、かつまだ \(f(v)\) が確定していない(\(v\) の部分木内の頂点であって、値が書き込まれていないものが存在する)頂点に限られます。

それらの頂点のうち、最も深いものを \(x\) とすると、Bob は \(x\) の部分木に含まれる値が書かれていない頂点を一つ選び値 \(K\) を書き込むことで、Alice が一手で勝利できない状態を保つことができます。

以上より示されました。

[2] 判定方法

命題の条件の判定は、各頂点について、子孫の頂点の個数及び子孫の中で各値それぞれについてその値が書かれた頂点の個数が分かればよいです。これは各頂点について dfs をしても \(\mathrm{O}(N^2)\) または \(\mathrm{O}(N^2\log N)\) などで十分高速です。

おまけ：マージテクを使うことで \(\mathrm{O}(N\log^2 N)\) で解くこともできます。