「両者が最適に行動したときの高橋君の得点が \(X\) 以上か？」という判定問題を解くことができれば、それが真となる最大の \(X\) を二分探索で求めることで本問題の答えが得られます。 よって、以下ではこの判定問題を解く方法を述べます。\(X \leq 0\) の場合は自明なため、\(X > 0\) を仮定します。

この判定問題を解くにあたっては、各頂点に書かれた整数が \(X\) 以上かどうかのみに注目すれば良いです。 そこで、\(A_i \geq X\) を満たす頂点 \(i\) を黒に、\(A_i < X\) を満たす頂点 \(i\) を白に塗ります。

そして、下記の白黒ゲームを考えます。

ゲームが終了するまで下記の手順 1. から手順 4. を繰り返す。

1. 現在コマがある頂点が黒のとき、高橋君の勝ちでゲームが終了する。
2. 現在コマがある頂点が葉ならば、青木君の勝ちでゲームが終了する。
3. 青木君が根以外の頂点を任意に \(1\) 個選び、その頂点を白で塗る。
4. 高橋君がコマを、いまコマがある頂点の子のどれかに移動する。

このとき、「判定問題の答えが真」であるのは、次が成り立つことと同値です。

頂点 \(1\) にコマが置かれた状態から白黒ゲームをはじめ、両者が最適に行動したときに高橋君が勝つ（すなわち、高橋君が必勝である）。

上の条件が成り立つかを動的計画法（いわゆる木 DP ）で求めます。 \(v = 1, 2, \ldots, N\) に対して、\(\mathrm{dp}[v]\) を次の通りに定義します。

頂点 \(v\) にコマが置かれた状態から白黒ゲームを始める。ただし、ゲームを始める前に、青木君は好きな個数（ \(0\) 個でも良い）の頂点を選んでそれらをあらかじめ白く塗ることができる。 ゲームが青木君の必勝となるために、青木君があらかじめ白く塗らなければならない頂点の個数の最小値を \(\mathrm{dp}[v]\) とする。

上の定義より、\(v = 1, 2, \ldots, N\) について、「頂点 \(v\) にコマが置かれた状態から白黒ゲームを始めると青木君が必勝である」ことは、\(\mathrm{dp}[v] = 0\) と同値です。 特に、所望の判定問題を解くには \(\mathrm{dp}[1] = 0\) かどうかがわかれば良いです。

頂点 \(v\) が \(k\) 個の子 \(c_1, c_2, \ldots, c_k\) を持つとき、 \(\mathrm{dp}[v]\) と \(\mathrm{dp}[c_1], \mathrm{dp}[c_2], \ldots \mathrm{dp}[c_k]\) の関係を以下で導きます。

まず、頂点 \(v\) が白のときを考えます。 頂点 \(v\) にコマがある状態から白黒ゲームを始めるとき、青木君が必勝となるためには青木君はゲーム開始前にいくつの頂点を白で塗る必要があるでしょうか？ 頂点 \(v\) にコマがある状態から始めて青木君が必勝であるには「高橋君が次にコマを \(v\) のどの子 \(c\) に進めたとしても、子 \(c\) にコマがある状態から白黒ゲーム（の続き）を始めたとき青木君が必勝」でなければなりません。 よって、青木君は高橋君がコマを進める直前までに、\(\sum_{i = 1}^k \mathrm{dp}[c_i]\) 個の黒い頂点を白く塗らなければなりません。 ゲームが始まってから高橋君がコマを進めるまでに、青木君は \(1\) 個の頂点を白く塗ることができるので、青木君がゲームが始まる前にあらかじめ白く塗らなければならない頂点数は \(\max \lbrace \sum_{i = 1}^k \mathrm{dp}[c_i] - 1, 0\rbrace\) 個です。 頂点 \(v\) が黒の場合は、さらに頂点 \(v\) もゲームが始まる前にあらかじめ白く塗る必要があります。

したがって、\(v = 1, 2, \ldots, N\) について \(B_v\) を、

• 頂点 \(v\) が黒のとき、\(B_v = 1\)
• 頂点 \(v\) が白のとき、\(B_v = 0\)

と定めると、\(v = 1, 2, \ldots, N\) について、

\[ \mathrm{dp}[v] = \max\Big\lbrace \displaystyle \sum_{c \in \mathcal{C}_v} \mathrm{dp}[c]-1, 0 \Big\rbrace + B_i \]

が成り立ちます。ここで、\(\mathcal{C}_v\) は頂点 \(v\) の子の集合であり、\(\mathcal{C}_v = \emptyset\) のときは \(\sum_{c \in \mathcal{C}_v} \mathrm{dp}[c] = 0\) とみなします。

上記の漸化式を用いて \(\mathrm{dp}[\ast]\) を再帰的に計算し \(\mathrm{dp}[1] = 0\) かを判定することで、与えられた \(X\) に対して判定問題を \(\mathrm{O}(N)\) 時間で解くことができます。

判定問題の答えが真となる最大の \(X\) を二分探索で求めることで、本問題を \(\mathrm{O}(N \log A_{\max})\) 時間で解くことができます。ここで、\(A_{\max} := \max_{1 \leq i \leq N} A_i\) です。