Maximum Root-to-Leaf Sum in a Tree

You are given a tree with n nodes. Each node has an integer value. The tree is rooted at node 1. Your task is to compute the maximum sum of values on any path from the root (node 1) to a leaf node.

A leaf is a node that has no children. Formally, if a path is given by
\(1 \rightarrow v_2 \rightarrow v_3 \rightarrow \cdots \rightarrow v_k\),
the sum along this path is
\(\text{value}_1 + \text{value}_{v_2} + \cdots + \text{value}_{v_k}\).
Find the maximum sum achievable among all root-to-leaf paths.

You can assume that the tree is connected and contains no cycles.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains an integer \(n\) (the number of nodes in the tree).
2. The second line contains \(n\) space-separated integers representing the values of the nodes (from node 1 to node \(n\)).
3. Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) which denote an edge between nodes \(u\) and \(v\).

outputFormat

Output a single integer to standard output (stdout) representing the maximum sum from the root (node 1) to any leaf.

## sample

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

11

</p>