Subtree Maximum Query

You are given an undirected tree with \(N\) nodes and \(N-1\) edges. Each node has an integer value, and node 1 is the root of the tree. Your task is to answer \(Q\) queries. Each query provides a node \(v\), and you are to determine the maximum value among all nodes in the subtree rooted at \(v\).

The subtree of a node \(v\) includes \(v\) itself and all of its descendants.

Note: The input is given via standard input (stdin) and the output should be printed to standard output (stdout).

inputFormat

The input is read from stdin and follows the format below:

N
v1 v2 ... vN
u1 v1
u2 v2
... (N-1 edges, each on a new line, representing an undirected edge between two nodes)
Q
q1 q2 ... qQ

Where:

• \(N\) is the number of nodes in the tree.
• Each \(v_i\) is the value associated with the \(i\)-th node.
• Each edge is given by two integers representing connected nodes (1-indexed).
• \(Q\) is the number of queries.
• Each \(q_i\) is a query representing a node, and you must find the maximum value in the subtree rooted at that node.

outputFormat

For each query, output the maximum value in the corresponding subtree on a new line. The output is to be written to stdout.

## sample

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

5
4
5

</p>