Maximum Subtree Weight

You are given a tree with n nodes. Each node is assigned a weight. The tree is provided in the form of n nodes along with n-1 edges connecting them.

Your task is to determine the maximum sum of weights among all subtrees of the given tree. A subtree is defined as any connected part of the tree.

Note: The input is given in the following format:

• The first line contains an integer \(n\), the number of nodes.
• The second line contains \(n\) space-separated integers representing the weights of the nodes (1-indexed).
• The third line contains an integer \(m\) (which is \(n-1\) for a valid tree) representing the number of edges.
• The following \(m\) lines each contain two space-separated integers \(u\) and \(v\) indicating an edge between node \(u\) and node \(v\).

The output should be a single integer which is the maximum weight sum of any subtree.

The DFS based solution below uses recursion to compute the subtree sums and tracks the maximum encountered sum.

inputFormat

The input is read from standard input (stdin) and formatted as follows:

• Line 1: An integer \(n\) representing the number of nodes.
• Line 2: \(n\) space-separated integers denoting the weights of the nodes.
• Line 3: An integer \(m\) representing the number of edges (typically \(n-1\)).
• The next \(m\) lines: Each line contains two integers \(u\) and \(v\) which describe an edge between nodes \(u\) and \(v\).

outputFormat

The output is read from standard output (stdout) and is a single integer: the maximum subtree weight sum.

The answer should be printed followed by a newline.

## sample

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

15

</p>