Magic Tree Maximum Path Sum

In the magical kingdom, there exists a unique tree known as the Magic Tree. The tree consists of n vertices and n-1 edges, ensuring it is connected and contains no cycles. Each vertex harbors a jewel with a certain jewel-value.

Your task is to determine the maximum possible sum of jewel-values along a valid path in the tree. In this context, a valid path is defined as a sequence of connected vertices where, starting from any vertex, you move to one of its neighbors. Note that although the path is not required to cover all vertices, the strategy is to choose a single branch at each vertex that yields the highest sum.

The mathematical formulation of the problem is as follows:

Given a tree with n vertices and a list of values \(a_1, a_2, \ldots, a_n\), you are to compute the maximum sum \(S\) along a path, where for a path \(v_1 \to v_2 \to \cdots \to v_k\), the sum is \(S = a_{v_1} + a_{v_2} + \cdots + a_{v_k}\).

inputFormat

The first line contains a single integer n, the number of vertices in the tree.

The second line contains n space-separated integers representing the jewel-values of the vertices.

Each of the next n-1 lines contains two space-separated integers u and v, denoting an edge between vertices u and v.

outputFormat

Output one integer: the maximum possible jewel-value sum along a valid path in the tree.

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

15