Subtree Maximum Values

Given an undirected tree with n nodes where each node has an associated integer value, your task is to compute for each node the maximum value in its subtree. Here, the subtree of a node is defined as the node itself plus all of its descendants when the tree is rooted at node 1.

Formally, for each node v, let \(S(v)\) denote the set consisting of v and all nodes in the subtree rooted at v. You are required to output an array such that the i-th element is given by:

\[ \max_{u \in S(i)} a_u \]

where \(a_u\) denotes the value at node \(u\).

You may assume that the input forms a valid tree and that node 1 is always the root.

inputFormat

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

n
a1 a2 ... an
u1 v1
u2 v2
... 
un-1 vn-1

Where:

• n is the number of nodes.
• The second line contains n integers representing the value at each node.
• Each of the next n-1 lines contains two integers u and v representing an edge between node u and node v.

outputFormat

Print a single line to standard output (stdout) containing n integers separated by spaces. The i-th integer should represent the maximum value in the subtree rooted at node i.

## sample

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

5 5 2 5 4