この問題は二分探索を用いることによって、特別なデータ構造を用いずに解くことが可能です。

まず、次のような問題を考えます。

ゲームが終了するまでに駒が訪れた頂点に書かれた数の集合の中央値が\(X\) 以上のとき太郎君の勝ち、\(X\) 未満の時次郎君の勝ちとします。両者が最善を尽くすとき、どちらが勝利するでしょうか。

この問題は公式解説と同じ発想で、全ての葉に対してその頂点でゲームが終了したときの勝敗が分かれば木DPで解くことができます。勝敗は、通った頂点に書かれていた数の集合\(S\) について、

• \(S\) の要素のうち、\(X\) より大きい/小さいものの数
• \(S\) の要素のうち、\(X\) 以上のものの中での最小値
• \(S\) の要素のうち、\(X\) 以下のものの中での最大値

を管理しておけば求めることができます。これらは\(O(1)\)で更新することができるので、DFSにより全体で\(O(N)\)で全ての葉についての勝敗を求めることができます。

\(X\) について二分探索を行うことにより、全体で\(O(N\) \( \mathrm {log}\) \(\mathrm {max}\) \( A)\)で問題の答えを求めることができます。

実装例(PyPy3)