Experiences#8724

Experiences

0.5 seconds

256 megabytes

Hard

Company X has $N$ employees. The company has a strict hierarchical tree-like structure – the CEO (Chief Executive Officer) stands at the top (root of the tree), he has some number of direct subordinates, who also have direct subordinates and so on, until we reach regular employees, who have no subordinates (leaves of the tree). The employees are numbered with integers from $1$ to $N$ . The CEO has number 1, but the other numbers have nothing to do with the hierarchy. Each employee has some experience – the $i$ -th employee has experience, denoted by non-negative integer $W_{i}$ W_i.

The company has a large number of group projects to complete and the management has decided to split all of the employees into different groups (teams), so that the following conditions are satisfied:

Each team must consist of at least one person and each person must belong to exactly one team.
Each team must consist only of people, who are consecutive subordinates of one another. A group of employees $j_{1}$ j_1, $j_{2}$ j_2, $j_{3}$ j_3, $j_{4}$ j_4 … is a valid team if $j_{2}$ j_2 is directly subordinate of $j_{1}$ j_1, $j_{3}$ j_3 is a directly subordinate of $j_{2}$ j_2, $j_{4}$ j_4 is directly subordinate of $j_{3}$ j_3 and so on.

The management knows that after a group project is finished, the total experience of the group, assigned to the project, increases by $W_{ma x} - W_{min}$ W_{max} - W_{min}, where $W_{ma x}$ W_{max} is the maximal experience, and $W_{min}$ W_{min} is the minimal experience among the group members. The total experience increase for the company is equal to the sum of the experience increases of all teams. The management wants to maximize the total experience increase for the company, by splitting the employees into the best possible teams' configuration, following the two conditions mentioned above.

Write a program experience to calculate the maximum possible experience increase for the company.

Input

The first line of the standard input contains a single integer $N$ - number of employees in the company ( $1 \leq N \leq 1 0^{5}$ 1 \leq N \leq 10^5).

The second line contains $N$ space separated non-negative integers $W_{1}, W_{2}, \dots, W_{N}$ W_1, W_2, \ldots, W_N – the experience of each employee of the company ( $0 \leq W_{i} \leq 1 0^{9}$ 0 \leq W_i \leq 10^9).

Then $N - 1$ N-1 lines follow, each containing space separated integers $u$ and $v$ in the mentioned order. These numbers represent the subordinate relations in the company – the employee with number $v$ is a direct subordinate of the employee with number $u$ .

Output

The program should print to the standard output one integer – the maximum total experience increase for the company.

Examples

Example 1

Note

One possible configuration that maximizes the total experience increase is {1, 5, 3}, {6, 2, 4}, {7}.

There is another configuration with the same maximal total experience increase – {1, 5}, {3}, {6, 2, 4}, {7}.