Problem Description

Xiao Ming wants to catch starfish on the seabed. The seabed is a tree-like structure, and the starfish are hidden inside it.

Given a tree with $n$ nodes, numbered $1, 2, 3, ..., n$, and the weight of node $i$ is denoted as $p_i$.

A starfish is defined as a “flower subgraph” in the tree. Assume its center node is labeled $O$, and its leaf (peripheral) nodes are labeled $a_1, a_2, ..., a_t$ (each leaf node must be directly connected to the center node, and the flower subgraph contains at least one center node and one leaf node). The value of this starfish is defined as $|p_O - \sum p_{a_i} |$.

Xiao Ming wants to know the maximum total value of starfish he can catch. (He may catch multiple starfish at the same time, but the intersection of the node sets of any two starfish must be empty.)

Additional definitions:

Flower graph: A connected graph with diameter less than or equal to $3$. The node with the largest degree is the center node, and all other nodes are leaf (peripheral) nodes (so every leaf node has degree $1$).

Example: The smallest flower graph is $(G,V)=({1,2},{(1,2)})$, which consists of only two nodes and the single edge connecting them.

Input Format

The first line contains a positive integer $n$, representing the size of the tree.

The second line contains $n$ integers, representing $p_i$.

Lines $3$ to $n + 1$ each contain two integers $a, b$, indicating that there is an edge between node $a$ and node $b$.

Output Format

Output one line containing one integer, representing the maximum total value of starfish Xiao Ming can catch.

5
-2 -3 4 -5 1
1 2
1 3
2 4
2 5

10

见/example/starfish/下

见/example/starfish/下

Hint

Sample Explanation

One valid plan is that Xiao Ming catches two starfish. The first starfish has center node $1$ and leaf node $3$, with value $6$. The second starfish has center node $2$ and leaf node $5$, with value $4$. In this case, the maximum total value is $10$.

Constraints

$(1)$ For $10\%$ of the testdata, the data is guaranteed to form a flower graph.

$(2)$ For $20\%$ of the testdata, the data is guaranteed to form a chain.

$(3)$ For $20\%$ of the testdata, it is guaranteed that the product of the weights of adjacent nodes is always negative.

$(4)$ For $20\%$ of the testdata, the data is guaranteed to form a binary tree rooted at $1$.

$(5)$ For $30\%$ of the testdata, there are no special constraints.

For all testdata, $1 \le a, b \le n \le 10^5$, $-10^9 \leq p_i \leq 10^8$.

In the provided samples, data numbered $i$ and $i + 5$ correspond to constraint group number $i$, where $i \in \{1, 2, 3, 4, 5\}$.

Translated by ChatGPT 5