Maximizing Experience Difference in Hierarchical Team Partitions

A company (X Company) has n employees organized in a tree‐like hierarchy. The CEO, numbered 1, is at the top; each other employee has exactly one direct manager and the organization forms a tree.

Each employee i has an associated experience value \(W_i\). The management wants to reorganize the company by splitting the tree into several teams. The partition must satisfy the following conditions:

• Each team is nonempty and every employee belongs to exactly one team.
• For any team, if you sort its members by their level in the original hierarchy from the lowest (i.e. the subordinate) to the highest (i.e. the manager), and denote them as \(\{j_1,j_2,\dots,j_k\}\), then for every \(i\) in \([1,k-1]\) employee \(j_i\) must be the direct manager of \(j_{i+1}\). In other words, each team must form a chain (a simple path upward in the tree).

Define the total experience of a team as the range of experience values among its members, i.e. the maximum experience minus the minimum experience in that team. The company’s overall experience value is the sum of the team experience values. Your task is to partition the employees into valid teams so that the overall experience value is maximized.

Note: If a team consists of a single employee, its experience value is 0.

The answer might involve careful choices since a manager with several subordinates can extend his/her team with at most one subordinate (to maintain the chain structure), while all other subordinates must start new teams.

inputFormat

The first line contains an integer n (\(1 \leq n \leq 10^5\)), the number of employees.

The second line contains n space‐separated integers: \(W_1, W_2, \dots, W_n\) where \(W_i\) is the experience value of the i-th employee.

The following n-1 lines each contain two integers u and v indicating that employee u is the direct manager of employee v (this edge is present in the tree). It is guaranteed that the employees form a tree with employee 1 as the root.

outputFormat

Output a single integer: the maximum total experience value the company can obtain by optimally partitioning the tree into teams as described.

sample

3
5 1 4
1 2
1 3

4