Description

In the $X$ forest, God created the Tree of Life.

He labeled each node of the tree (a leaf is also a node) with an integer, which represents the harmony value of that node.

God wants to choose a set of nodes $S$ (the empty set is allowed) such that for any two nodes $a, b$ in $S$, there exists a sequence of nodes ${a, v_1, v_2, \cdots, v_k, b}$ where every node in the sequence is an element of $S$, and every pair of adjacent nodes in the sequence is connected by an edge.

Under this condition, God wants to maximize the sum of the integers corresponding to the nodes in $S$.

This maximum sum is the score God gives to the Tree of Life.

With atm's efforts, he already knows the integer on each node of the tree. However, since atm is not good at calculations, he does not know how to compute the score efficiently. He needs you to write a program to compute the score of a tree.

Input Format

The first line contains an integer $n$, indicating that the tree has $n$ nodes.

The second line contains $n$ integers, in order, representing the score of each node.

The next $n - 1$ lines each contain $2$ integers $u, v$, indicating that there is an edge between $u$ and $v$. Since this is a tree, there are no cycles.

Output Format

Output one number in a single line, representing the score God gives to this tree.

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

8

Hint

For $30\%$ of the testdata, $n \le 10$.

For $100\%$ of the testdata, $0 < n \le 10^5$, and the absolute value of each node's score does not exceed $10^6$.

Time limit: 3 seconds. Memory limit: 256 MB.

Lanqiao Cup 2015 Provincial Contest B Group, Problem J.

Translated by ChatGPT 5