We can rephrase the following:

Condition 2: \(|E_i - E_j| \geq dist(i, j)\) holds for every pair \((i, j)\) \((1 \leq i < j \leq N)\).

into the following:

Condition 2: Assume \(E_{p_1} < E_{p_2} < E_{p_3} < \cdots < E_{p_N}\). Then, \(dist(p_i, p_{i+1}) \leq E_{p_{i+1}} - E_{p_i}\) holds for every pair \(1 \leq i \leq N-1\).

because \(dist(p_L, p_R) \leq dist(p_{L}, p_{L+1}) + dist(p_{L+1}, p_{L+2}) + \cdots + dist(p_{R-1}, p_R)\) holds for any \(L, R\).

Thus, to minimize the maximum among \(E_i\), we should set them as follows:

Condition 2 + Condition 3: \(dist(p_i, p_{i+1}) = E_{p_{i+1}} - E_{p_i}\) for every \(1 \leq i \leq N-1\).

The minimum among \(E_i\) will be \(1\), so the maximum among \(E_i\) will be \(dist(p_1, p_2) + dist(p_2, p_3) + \cdots dist(p_{N-1}, p_N) + 1\). Now we want to find the following:

We will start at some vertex and visit all the vertices. What is the order to visit the vertices \(p_1 \to p_2 \to \cdots \to p_N\) that minimizes the total distance traveled?

For that, we can use the following fact:

To start at some vertex, visit all the vertices, and return to the starting point, we need to travel a distance of at least \(2(N-1)\) in total.

The figure below describes this fact:

Now, let us consider the following problem:

• Visit all \(N\) vertices with the shortest possible distance traveled. Here, we must start at Vertex \(s\) and end at Vertex \(t\).

In this case, the shortest possible distance is \(2(N-1) - dist(s, t)\), which can be achieved as follows:

• Do a depth-first search from Vertex \(s\), traversing the vertices in pre-order.
• However, make sure that the edge going to Vertex \(t\) is traversed last.

The figure below illustrates some examples:

Thus, we can choose \(s, t\) that maximize \(dist(s, t)\) to minimize \(2(N - 1) - dist(s, t)\), the distance traveled. This maximum distance is called the diameter of a tree, which is known to be found in linear time.

Writer’s code: https://atcoder.jp/contests/arc117/submissions/21730882

Tester’s code: https://atcoder.jp/contests/arc117/submissions/21780162

Bonus: can you write the code that judges submissions to this problem? That is, given a description of a tree \(N, A_i, B_i\) and an output of a contestant \(E_i\), determine whether the output satisfies the conditions. Our solution runs in \(O(N \log N)\) time.