Bug on a Tree

A tree is a connected graph with no cycles. In this problem, the tree is not rooted. Each edge represents a branch, and each vertex represents a point on the tree where fruit may be hanging. A vertex may have zero fruit.

One bug is on the tree. The bug may start moving from any vertex. Whenever it is at a vertex, it eats all fruit on that vertex. Then, if there is an incident edge it has not used before, it moves along one such edge to another vertex. An edge that has already been used cannot be used again. Since the graph is a tree, the bug's route is a simple path and eventually ends at a vertex where it has no unused edge to take.

Given the shape of the tree and the amount of fruit on each vertex, find the maximum number of fruit the bug can eat and the starting vertex that achieves that maximum. If several starting vertices are possible, choose the smallest numbered one.

The first line contains an integer n (1 <= n <= 10,000), the number of vertices in the tree.

The next line contains n integers. The i-th integer is the number of fruit hanging on vertex i.

Each of the next n - 1 lines contains two integers A and B (1 <= A, B <= n), meaning that vertices A and B are connected by an edge.

The total number of fruit on the tree does not exceed 2^31 - 1 (2,147,483,647).

Print two integers on one line: the maximum number of fruit the bug can eat, and the vertex number where it should start.

If there is more than one valid starting vertex, print the smallest vertex number.