Maximum Path Cost in a Tree

You are given a tree with n nodes (numbered from 1 to n) and n-1 edges. Each node is assigned an integer value. A path in the tree is a sequence of nodes where each consecutive pair is connected by an edge. The cost of a path is defined as the sum of the values of all nodes present in that path.

Your task is to compute the maximum cost over all possible paths in the tree.

The problem can be formally stated as follows:

$$\text{Maximum Cost} = \max_{P \in \mathcal{P}} \sum_{v \in P} a_v$$

where \(\mathcal{P}\) is the set of all paths in the tree and \(a_v\) is the value assigned to node \(v\).

inputFormat

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

1. An integer n representing the number of nodes in the tree.
2. A line containing n integers, where the i-th integer denotes the value assigned to node i.
3. n-1 lines follow, each containing two integers u and v which represent an edge connecting nodes u and v (nodes are 1-indexed).

outputFormat

Output via standard output (stdout) a single integer representing the maximum path cost in the tree.

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

15