Description

Xiao Ming is very interested in mathematics and is a diligent student who always stays after class to ask the teacher questions. One morning on his way to school by bike, he saw an old man trimming plants and suddenly thought of a problem about pruning flowers. After class that day, Xiao Ming presented the following problem to his teacher:

There is a strange plant with $n$ flowers in total, connected by $n - 1$ branches so that before pruning, no flower is isolated. Each flower has a “beauty index,” where a larger value means the flower is more beautiful; some beauty indices can be negative, meaning the flower looks unpleasant. “Pruning” means removing one of the branches, which splits the plant into two, and then discarding one of them. After a sequence of prunings, only one plant remains (which could be a single flower). The task is to perform a sequence of prunings (or none at all) to maximize the sum of the beauty indices of all flowers on the remaining plant.

The teacher quickly gave the correct solution. Seeing the problem solved so easily, Xiao Ming felt unsatisfied and brought it to you.

Input Format

• The first line contains an integer $n$ ($1 \le n \le 16000$), the number of flowers on the original plant.
• The second line contains $n$ integers. The $i$-th integer is the beauty index of the $i$-th flower.
• The next $n - 1$ lines each contain two integers $a, b$, indicating there is a branch connecting the $a$-th flower and the $b$-th flower.

Output Format

Output a single integer, the maximum possible sum of beauty indices after a sequence of prunings. The absolute value is guaranteed not to exceed $2147483647$.

7
-1 -1 -1 1 1 1 0
1 4
2 5
3 6
4 7
5 7
6 7

3

Hint

Constraints

• For $60\%$ of the testdata, $1 \le n \le 1000$.
• For $100\%$ of the testdata, $1 \le n \le 16000$.

Translated by ChatGPT 5