Maximum Sum Root-to-Leaf Path in a Tree

You are given a tree with n nodes. Each node is assigned a value. The tree is provided as n node values and n-1 edges. The tree is rooted at node 1. Your task is to compute the maximum sum of values along any path from the root node to a leaf node.

The answer should be computed using the formula:

\(\text{maxSum} = \max_{\text{path from root to leaf}}\sum_{i \in \text{path}} value_i\)

A leaf is defined as a node that has no children (except possibly the parent from which it was reached in the tree).

inputFormat

The first line contains an integer n (the number of nodes).

The second line contains n integers representing the values of nodes 1 through n.

Each of the next n-1 lines contains two integers u and v, indicating that there is an edge between nodes u and v.

outputFormat

Output a single integer, the maximum sum of values from the root (node 1) to any leaf node.

1
5

5