Maximum Path Sum in a Tree

Given a tree with \( N \) nodes where each node has an associated value, your task is to find the maximum possible sum of values along any simple path in the tree. A simple path is defined as a sequence of distinct nodes where each consecutive pair of nodes is connected by an edge.

One hint is to use Depth-First Search (DFS) to calculate, for each node, the maximum branch sum that can be obtained from its subtrees. Then at each node, by combining the two greatest branch sums from its children (if they exist) with the node's own value, you can update the global maximum path sum.

The final answer should be output as a single integer.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains an integer \( N \) (\( 2 \le N \le 10^5 \)), representing the number of nodes in the tree.
• The second line contains \( N \) integers representing the values of the nodes.
• Each of the next \( N-1 \) lines contains two integers \( u \) and \( v \), denoting an edge between node \( u \) and node \( v \).

outputFormat

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

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

12