Maximum Sum Path and Longest Path Length in a Tree

You are given a tree with n nodes. Each node is assigned an integer value. Your task is to find a simple path in the tree such that:

• The sum of the values along the path is maximized.
• If there are multiple paths with the same maximum sum, choose the one with the greatest number of nodes.

Formally, let the tree be represented as an undirected graph with n nodes, and let \(a_i\) be the value on node \(i\). A path is a sequence of nodes \(v_1, v_2, \dots, v_k\) such that for each \(1 \le i < k\), there is an edge between \(v_i\) and \(v_{i+1}\). You need to compute the maximum possible value of \(\sum_{i=1}^{k} a_{v_i}\) and the corresponding path length \(k\) (i.e. the number of nodes in the path).

Note: The input guarantees that the given graph is a tree (i.e. connected and acyclic).

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains an integer n, the number of nodes in the tree.
The second line contains n space-separated integers, representing the values assigned to each node in order from node 1 to node n.
Each of the following n-1 lines contains two space-separated integers u and v, indicating that there is an undirected edge between nodes u and v.

outputFormat

Print to standard output (stdout) two space-separated integers: the maximum sum along a path in the tree and the number of nodes on that path.

If multiple paths yield the same maximum sum, the path with the greatest length should be chosen.

5
3 2 1 10 1
1 2
1 3
2 4
2 5

16 4