405064: GYM101773 D Unsmooth Tree

Dmitriy likes trees and does not like when things change fast. He even created a notion of tree unsmoothness. A tree consisting of n vertices indexed from 1 to n with each vertex i assigned some real value x_i has a value of unsmoothness equal to the largest of roughness values of its edges. A roughness value of an edge connecting vertices i and j is defined as |x_i - x_j|.

Dmitriy had a tree on a table that was pretty smooth. One day he returned to his table back from lunch and found out that his colleague Andrew erased some of the numbers x_i. Dmitriy does not remember the exact values of lost x_i, but he sees this as an opportunity to make his tree even more smooth!

Find out the minimum possible value of unsmoothness of his the tree that Dmitriy may achieve if he fills the erased values of x_i properly.

The first line of input contains an integer n (2 ≤ n ≤ 100 000), the number of vertices in the tree.

The second line of input contains n tokens x₁, x₂, ..., x_n (either x_i is an integer and  - 10⁶ ≤ x_i ≤ 10⁶ or x_i = '*' which denotes the erased number).

The i-th of the following n - 1 lines contains two integers u_i, v_i (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i), indices of the vertices connected by the i-th edge.

Output the only number, the minimum possible smoothness of the resulting tree after Dmitry fills all the erased values.

Your answer will be considered correct if its relative or absolute error does not exceed 10^- 6.

4
-1 4 * 2
1 3
4 3
3 2

2.5

3
* 2 *
3 1
2 1

0

In the first sample test the optimal way to fill the only erased value is to put 1.5 there. In such way the roughness of the edge (1, 3) is 2.5, the roughness of the edge (4, 3) is 0.5 and the roughness of the edge (3, 2) is 2.5. Thus, the unsmoothness of the tree equals to 2.5.

In the second sample test the optimal way to fill the erase values is to put 2 for both vertices. In this way both edges have roughness of 0, and the unsmoothness of the tree also equals to 0.