4488: G. Group Homework
内存限制：512 MB
时间限制：3 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：0
通过：0
题目描述
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 ai. 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 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 ai. 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 <= n <= 2 × 105), denoting the number of vertices.
The second line contains n integers separated by spaces, the i-th integer denotes ai (1 <= ai <= 104).
In the following n - 1 lines, each contains two integers u, v (1 <= u, v <= n), denoting (u, v) is a tree edge.
It is guaranteed that the input edges form a tree of n vertices.
The second line contains n integers separated by spaces, the i-th integer denotes ai (1 <= ai <= 104).
In the following n - 1 lines, each contains two integers u, v (1 <= u, v <= 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
数据范围与提示
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.
input
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.
input
1 1output
0input
3 1 2 3 1 2 2 3output
6