Maximum Downward Path Sum in a Tree

You are given a tree with n nodes. Each node has an integer value. The tree is provided as an undirected connected graph with n-1 edges. A downward path is defined as a sequence of nodes where each consecutive pair is connected by an edge, and no node is repeated; however, the path must be chosen in such a way that when exploring from any starting node, you never go back to the node from which you arrived. In other words, when moving from a node to any of its neighbors, the neighbor from which you came is excluded.

Your task is to determine the maximum sum of node values along any downward path in the tree. Formally, if you denote the value of node i as \(a_i\) and a valid downward path as \(i_1 \to i_2 \to \cdots \to i_k\), the sum is defined as \(a_{i_1} + a_{i_2} + \cdots + a_{i_k}\). Find the maximum such sum over all possible downward paths.

Note: The path can consist of a single node. Use appropriate algorithms such as depth-first search (DFS) to traverse the tree and compute the maximum sum.

inputFormat

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

1. The first line contains a single integer \(n\) \( (1 \le n \le 10^5)\), representing the number of nodes in the tree.
2. The second line contains \(n\) space-separated integers where the \(i\)-th integer represents the value \(a_i\) of the \(i\)-th node.
3. The next \(n-1\) lines each contain two space-separated integers \(u\) and \(v\) (\(1 \le u, v \le n\)), indicating that there is an undirected edge connecting nodes \(u\) and \(v\).

outputFormat

Print a single integer to standard output (stdout) representing the maximum sum of values along any downward path in the tree.

5
10 2 10 -1 3
1 2
1 3
3 4
3 5

23