Maximum Sum Path in a Tree

Given a tree with N nodes, where each node has an assigned value (indexed from 1), determine the maximum sum achievable on any path from the root (node 1) to a leaf node. A leaf node is defined as a node with no children.

The tree is provided as follows: The first line contains an integer N, followed by a line with N space-separated integers representing the node values. Then, N-1 lines follow, each containing two integers that define an edge connecting two nodes. The tree is guaranteed to be connected.

Your goal is to compute the sum of node values along the path from the root to any leaf such that the sum is maximized.

inputFormat

The input is read from standard input (stdin). The first line contains an integer N (1 ≤ N ≤ 10^5), representing the number of nodes. The second line contains N space-separated integers, where the i-th integer is the value of node i. Each of the next N-1 lines contains two space-separated integers u and v, indicating an edge between nodes u and v.

outputFormat

Output a single integer — the maximum sum of node values on any path from the root (node 1) to a leaf node.## sample

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

8