410310: GYM104008 G Group Homework

No, we don't want group homework. It's the place where $$$1 + 1 < 1$$$ can be true. However, you are currently the leader of a group with three members. Luckily, your group members will write everything down for you since you are the prestigious leader. Unluckily, you have to assign the new algorithm homework to your two team members, Mr. Dian and Mr. Beng, who can't understand the ideas of each other correctly and mess up all the details in the cooperation.

The new homework is about a tree: there are $$$n$$$ vertices on the tree with $$$n - 1$$$ bidirectional edges connecting them. Each vertex $$$i$$$ is a problem with a score of $$$a_i$$$. You can assign a tree path to each member, then Mr. Dian and Mr. Beng will solve the problems on their path independently. The final score of the homework is decided by the sum of the scores of the vertices visited by exactly one member — as we mentioned before, if both of them solved one problem independently, they will argue a lot about who is right, and all the effort will be in vain.

Now, you — Mr. Ji — want to maximize the final score (as well as the chance not to drop out of school due to too low GPA). Make a wise choice!

The first line of input contains a single integer $$$n\, (1 \leq n \leq 2 \times 10^5)$$$, denoting the number of vertices.

The second line contains $$$n$$$ integers separated by spaces, the $$$i$$$-th integer denotes $$$a_i\, (1 \leq a_i \leq 10^4)$$$.

In the following $$$n - 1$$$ lines, each contains two integers $$$u, v\, (1 \leq u, v \leq n)$$$, denoting $$$(u, v)$$$ is a tree edge.

It is guaranteed that the input edges form a tree of $$$n$$$ vertices.

Print an interger in a single line, denoting the maximum score if assigning paths optimally.

5
1 9 9 9 9
1 2
1 3
1 4
1 5

36

1
1

0

3
1 2 3
1 2
2 3

6

One optimal solution for sample case $$$1$$$ is $$$(2, 3), (4, 5)$$$. Two paths will intersect at $$$1$$$, and we can have all the remaining scores.

Note that you must assign exactly two paths to your dear group members. Therefore, for sample case $$$2$$$, you can only assign $$$(1, 1), (1, 1)$$$ to Mr. Dian and Mr. Beng, which leads to a pretty $$$0$$$ score.