Maximum Path Sum in a Binary Tree

You are given a binary tree with n nodes. The nodes are provided in level-order, and the tree is constructed using a list of edges. Each edge is represented by a pair of integers (u, v) meaning that node u is attached to node v as a child. When attaching nodes, if node v does not have a left child, assign node u to its left; otherwise, assign node u to its right.

Your task is to compute the maximum path sum in the binary tree. A path is defined as a sequence of nodes where each pair of consecutive nodes in the sequence is connected by an edge. Each node may appear at most once in the path and the path does not need to pass through the root.

The answer should be the maximum sum of the node values along any valid path. Note that the tree may contain negative values. In mathematical terms, if you denote the value of node i as \(a_i\), you need to find a path \(i_1, i_2, \dots, i_k\) such that the sum \(\sum_{j=1}^{k} a_{i_j}\) is maximized.

Input Constraints: \(1 \le n \le 10^5\). Node values can be both positive or negative.

inputFormat

Input is given via standard input in the following format:

1. A single integer n representing the number of nodes.
2. A line containing n space-separated integers representing the node values in level order.
3. A single integer m representing the number of edges (for a tree, typically m = n - 1).
4. m lines follow, each containing two integers u and v indicating that node u is attached to node v (i.e. v is the parent) according to the rule: if the left child of v is empty then assign u as left child, otherwise assign it as right child.

It is guaranteed that the given edges form a valid binary tree.

outputFormat

Output a single integer via standard output: the maximum path sum of the binary tree.## sample

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

11