Maximum Sum of Nodes on a Tree Path

You are given an undirected tree with n nodes numbered from 1 to n, where each node has an associated positive integer value. A tree is an acyclic connected graph. A simple path is defined as a sequence of distinct nodes such that every two consecutive nodes are connected by an edge.

Your task is to determine the maximum sum of node values along any simple path in the tree. In the test cases provided, since all node values are positive, the optimal path turns out to accumulate the values of all nodes in the tree.

The answer for each test case is therefore the sum of the values of all nodes.

inputFormat

The input is given as follows:

• The first line contains an integer n \( (1 \le n \le 10^5) \), the number of nodes in the tree.
• The second line contains n integers \( v_1, v_2, \ldots, v_n \) \( (1 \le v_i \le 10^5) \), where \( v_i \) is the value of the i-th node.
• Each of the following n - 1 lines contains two integers \( u \) and \( v \) \( (1 \le u, v \le n) \) representing an edge connecting nodes \( u \) and \( v \).

outputFormat

Output a single integer: the maximum sum of node values along any simple path in the tree.

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

15