Description

Company X has $n$ employees. The relationships among the employees form a tree structure. The CEO is at the top of the structure (the root of the tree). The CEO has some subordinates (the children of the root), and those subordinates have their own subordinates, and so on. Finally, there are some bottom-level employees (the leaves) who have no subordinates.

The employees are numbered from $1$ to $n$, and the CEO is employee $1$. Each employee has an experience value. The experience value of employee $i$ is $W_i$.

The company has a large project to complete, so the managers want to split and reorganize this tree structure into smaller teams. The splitting must follow these rules:

• Each team contains at least one person, and each employee must belong to exactly one team.
• For any team, suppose its members, sorted from lower rank to higher rank in the original hierarchy, are $\{j_1, j_2, j_3, ..., j_k\}$. Then it must hold that: for all $i \in [1, k-1]$, $j_i$ is the manager of $j_{i+1}$.

Define the total experience value of a team as the range of experience values among all members of that team; in other words, the maximum experience value in the team minus the minimum experience value in the team. The total experience value of the whole company is the sum of the experience values of all teams.

Your task is to find the maximum total experience value the company can obtain.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers: $W_1, W_2, ..., W_n$.

The next $n - 1$ lines each contain two integers $u, v$, indicating that $v$ is a subordinate of $u$.

Output Format

Output one integer representing the answer.

7
5 5 3 6 2 3 3
1 6
5 3
1 5
6 2
2 4
6 7

6

Hint

Explanation of Sample 1

One possible grouping is $\{1, 5, 3\}, \{6, 2, 4\}, \{7\}$.

Another possible grouping is $\{1, 5\}, \{3\}, \{6, 2, 4\}, \{7\}$.

Constraints

• For about $20\%$ of the testdata, it is guaranteed that $n \le 20$.
• For about $50\%$ of the testdata, it is guaranteed that $n \le 5 \times 10^3$.
• For another about $10\%$ of the testdata, it is guaranteed that each employee has at most one subordinate.
• For all testdata, it is guaranteed that $1 \le n \le 10^5$ and $0 \le W_i \le 10^9$.

Notes

The original problem is from: eJOI2017 Problem E Experience.

Translation provided by: @_Wallace_.

Translated by ChatGPT 5