This problem can be solved with a technique so-called 01 on Tree in Japan.

First, let us represent the strategy of treasure hunting using a permutation \(q = (q_0, q_1, \dots, q_N)\) of \((0, 1, \dots, N)\). Here, \(q\) represents the following strategy:

• \(q_0 = 0\).
• First, inspect \(q_1\). If the treasure is found, terminate the procedure.
• Next, inspect \(q_2\). If the treasure is found, terminate the procedure.
• \(\vdots\)
• Finally, inspect \(q_N\).

\(q\) is a legitimate strategy if and only if:

• for all \(1 \leq i \leq N\), value \(p_i\) appears prior to \(i\) in \(q\).

For convenience, let \(a_0 = 0\) and \(S = \sum_{i=1}^N a_i\). Then the expected number \(E(q)\) of operations in strategy \(q\) is represented as:

\[ \begin{aligned} E(q) &= \sum_{i=1}^N i \times \frac{a_{q_i}}{S} \\ &= \frac{1}{S} \sum_{i=0}^N i \times a_{q_i}. \end{aligned} \]

This problem asks to minimize \(E(q)\). Ignoring the constant factor \(\frac{1}{S}\), it has turned out that it is sufficient to minimize \(\sum_{i=0}^N i \times a_{q_i}\).

After all, it is enough to solve the following problem:

Rephrased problem (1)

Given an \((N+1)\)-vertex rooted tree, find a permutation \((q_0, q_1, \dots, q_N)\), subject to the following condition, that minimizes \(\sum_{i=0}^N i \times a_{q_i}\):

• for all \(1 \leq i \leq N\), the vertex number of the parent of \(i\) occurs prior to \(i\) in \(q\).

This is almost equivalent to 01 on Tree (link). The summary of 01 on Tree is as follows:

Summary of 01 on Tree:

Given an \(N\)-vertex rooted tree and a \(01\)-sequence \((V_1,V_2,\dots,V_N)\),
find a permutation \((q_1, \dots, q_N)\), subject to the following condition, that minimizes the inversion number of \((V_{q_1}, V_{q_2},\dots,V_{q_N})\):

• for all \(2 \leq i \leq N\), the vertex number of the parent of \(i\) occurs prior to \(i\) in \(q\).

To simplify the explanation, let us boil down the rephrased problem to 01 on Tree. The Rephrased problem (1) can be reworded using inversion numbers as follows, which obviously subsumes 01 on Tree:

Rephrased problem (2)

You are given an \((N+1)\)-vertex rooted tree. Vertex \(i\) has \(V_i = (0, 0, \dots, 0, 1)\) (\(0\) repeated \(a_i\) times) written on it.

Find a permutation \((q_1, \dots, q_N)\), subject to the following condition, that minimizes the inversion number of the concatenation of \(V_{q_0}, V_{q_1}, \dots, V_{q_N}\) in this order:

• for all \(1 \leq i \leq N\), the vertex number of the parent of \(i\) occurs prior to \(i\) in \(q\).

This problem can be solved by the following procedure. (We referred to the editorial of 01 on Tree to write this solution.)
First, let \(C_{0,i}\) be the number of \(0\)s in the sequence written on vertex \(i\), and \(C_{1,i}\) be that of \(1\)s. Let \(v\) be a (any) vertex with the maximum \(\frac{C_{0,i}}{C_{1,i}}\), and \(p\) be the parent vertex of \(v\).
Then, we can confirm that there exists a permutation \(p\) such that in which \(v\) occurs immediately to the right of \(p\) (because, otherwise we can move \(v\) to the left without a loss). Thus, we may construct a new tree by contracting vertices \(p\) and \(v\) while preserving the ancestor-descendant structure, and solve the problem on this new tree. (On this contracted vertex, we write the concatenation of \(V_p\) and \(V_v\) in this order.) We may perform this operation until we have only one vertex in the tree to solve the problem.
While this algorithm does yield the correct answer, naively searching for \(v\) and merging it with \(p\) costs a total of \(\mathrm{O}(N^2)\) time. This part can be reduced to \(\mathrm{O}(N \log N)\) using a priority queue and disjoint set union. (This is non-trivial, but the difficulty would be worth blue or yellow coders, so we are omitting the details here.) Also, the inversion number can be computed fast by appropriately processing the delta when merging vertices.

By implementing the algorithm so far, this problem can be solved in a total of about \(\mathrm{O}(N \log N)\) time, which is fast enough.