Maximum Path Sum in a Tree

You are given a tree with n nodes. Each node is assigned an integer value. Your task is to find the maximum possible sum of node values along any simple path in the tree. A simple path is a sequence of nodes where each consecutive pair of nodes is connected by an edge and no node is repeated.

The problem can be formulated as follows. Given an undirected tree, with its nodes numbered from 1 to n, an array \(a_1, a_2, \dots, a_n\) representing the node values, and \(n-1\) edges connecting the nodes, find the maximum value of \[ \text{max down dfs}(a_{i_1} + a_{i_2} + \cdots + a_{i_k}) \] where \(i_1, i_2, \dots, i_k\) is any simple path in the tree.

Note: The path does not need to pass through the root, and it can start and end at any node in the tree.

inputFormat

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

The first line contains a single integer n (1 ≤ n ≤ 105), the number of nodes in the tree.
The second line contains n space-separated integers representing the values of the nodes: \(a_1, a_2, \dots, a_n\).
Each of the next n-1 lines contains two integers \(u\) and \(v\) (1 ≤ u, v ≤ n) which denote an undirected edge between nodes u and v.

If n = 1, then there will be no edge lines.

outputFormat

Output a single integer, which is the maximum sum of node values along any simple path in the tree. The output should be written to standard output (stdout).

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

11