Maximum Path Sum in a Tree

You are given a tree with n nodes where each node has an associated weight. Your task is to find a simple path in the tree such that the total sum of weights along the path is maximized.

The tree is an undirected, connected acyclic graph. A path is defined as a sequence of nodes where every consecutive pair of nodes is connected by an edge and no node is repeated within the path.

One effective approach is to use a depth-first search (DFS). For each node, consider the two highest contributions from its subtrees. Mathematically, if for a given node, the two largest values obtained from its children are \(x\) and \(y\), then the global maximum candidate at that node is:

$$w_{node} + x + y$$

where \(w_{node}\) is the weight of the current node.

inputFormat

The input is given via standard input (stdin) as follows:

• The first line contains an integer \(n\) representing the number of nodes.
• The second line contains \(n\) space-separated integers, where the \(i\)-th integer is the weight of node \(i\).
• The following \(n-1\) lines each contain two integers \(u\) and \(v\), denoting an edge between nodes \(u\) and \(v\).

outputFormat

Output a single integer to standard output (stdout) which is the maximum sum of weights along any path in the tree.

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

11