Maximum Path Sum in a Binary Tree

Given a binary tree with (n) nodes, where each node carries an integer value, your task is to find the maximum path sum. A path is defined as any sequence of nodes connected by edges, where each node is visited at most once. The path does not need to pass through the root, and it can start and end at any node. The maximum path sum for a node is calculated as:

[ max_path = \max(, node.value,; node.value + left,; node.value + right,; node.value + left + right \ ) ]

where (left) and (right) represent the maximum sums from the left and right subtrees (only considering non-negative contributions). The input tree is constructed using a list of undirected edges and corresponding node values. Solve the problem by reading from standard input and writing the result to standard output.

inputFormat

The input is provided via standard input (stdin). 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 of the nodes (from 1 to (n)). Each of the following (n-1) lines contains two space-separated integers (u) and (v), indicating an undirected edge between nodes (u) and (v).

outputFormat

Output a single integer to standard output (stdout), which is the maximum path sum obtainable in the binary tree.## sample

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

42