If we can efficiently answer the question “can Takahashi’s score when both players played optimally be at least \(X\)?”, then the answer for the original problem can be achieved by finding maximum \(X\) that the answer for the question is “Yes” with binary search. We will now describe how to answer this question. The answer for \(X \leq 0\) is obvious, for we assume \(X > 0\).

In order to solve this problem, we are only interested in whether the integer written on each integer is at least \(X\) or not, so let us paint Vertex \(i\) such that \(A_i \geq X\) black, and Vertex \(i\) such that \(A_i < X\) white.

Now, consider the following Black-and-White Game.

Until the game ends, repeat the following Step 1. through Step 4..

1. If the piece is currently on a vertex painted black, then Takahashi wins and the game ends.
2. If the piece is currently on a leaf, then Aoki wins and the game ends.
3. Aoki chooses a vertex other than the root arbitrarily and paint it white.
4. Takahashi moves the piece to one of the children of the vertex the piece is currently on.

The answer for the question is “Yes” if and only if:

when they play Black-and-White Game optimally, with a piece initially on Vertex \(1\), Takahashi always wins.

Let’s determine if the condition above is met with Dynamic Programming (DP) (so-called “DP on tree”.) For \(v = 1, 2, \ldots, N\), we define \(\mathrm{dp}[v]\) as follows.

They play Black-and-White Game, with a piece initially on Vertex \(v\). Before the game starts, Aoki can choose any number of (possible zero) vertices to paint white. \(\mathrm{dp}[v]\) is the minimum number of vertices required for Aoki to win.

By the definition above, for \(v = 1, 2, \ldots, N\), “Aoki always wins when they play Black-and-White Game with the piece initially on Vertex \(v\)” if and only if \(\mathrm{dp}[v] = 0\). Especially, the answer for the question can be determined by whether \(\mathrm{dp}[1] = 0\).

Suppose that Vertex \(v\) has \(k\) children \(c_1, c_2, \ldots, c_k\). We derive the relation between \(\mathrm{dp}[v]\) and \(\mathrm{dp}[c_1], \mathrm{dp}[c_2], \ldots \mathrm{dp}[c_k]\).

First, suppose that Vertex \(v\) is white. When they starts Black-and-White Game with the piece initially on Vertex \(v\), how many vertices should Aoki paint white before the game starts if he want to win? If Aoki will always win the game with the piece initially on Vertex \(v\), it is necessary that “no matter which children \(c\) Takahashi chooses to move the piece in his next turn, Aoki will always win when they plays the (continued) Black-and-White Game with the piece initially on Vertex \(c\).” Therefore, by the time Takahashi moves the piece, Aoki has to paint \(\sum_{i = 1}^k \mathrm{dp}[c_i]\) black vertices white. Since Aoki can paint white at most one vertex since the game starts until Takahashi moves the piece, the number of vertices he has to paint white before the game starts is \(\max \lbrace \sum_{i = 1}^k \mathrm{dp}[c_i] - 1, 0\rbrace\). If Vertex \(v\) is also black, then Vertex \(v\) should also be painted white beforehand too.

Therefore, for \(v = 1, 2, \ldots, N\), let \(B_v\) be

• \(B_v = 1\) if Vertex \(v\) is black;
• \(B_v = 0\) if Vertex \(v\) is white,

then for \(v = 1, 2, \ldots, N\), it holds that

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

where \(\mathcal{C}_v\) is a set of children of Vertex \(v\), and if \(\mathcal{C}_v = \emptyset\), we assume that \(\sum_{c \in \mathcal{C}_v} \mathrm{dp}[c] = 0\).

By computing \(\mathrm{dp}[\ast]\) recursively based on the recurrence relation above and determining if \(\mathrm{dp}[1] = 0\), the question can be answered for any given \(X\) in an \(\mathrm{O}(N)\) time.

By finding maximum \(X\) that the answer for the question is “Yes” with binary search, the original problem can be solved in a total of \(\mathrm{O}(N \log A_{\max})\) time, where \(A_{\max} := \max_{1 \leq i \leq N} A_i\).