Subtree Minimums in a Rooted Tree

You are given a tree with (n) nodes labeled from 1 to (n). Each node has a unique value assigned to it. The tree is rooted at node 1. For every node (i), determine the minimum value in the subtree rooted at (i) (including the node itself). A tree is an undirected acyclic connected graph. Your task is to output the minimum value for each node's subtree in order from node 1 to node (n).

inputFormat

The input is given via standard input (stdin) in the following format:\ The first line contains one integer (n) (the number of nodes).\ The second line contains (n) space-separated integers, where the (i)th integer represents the value of node (i).\ Each of the next (n-1) lines contains two space-separated integers (u) and (v) representing an edge between nodes (u) and (v). It is guaranteed that the given edges form a tree, and the tree is rooted at node 1.

outputFormat

Print (n) space-separated integers on a single line, where the (i)th integer is the minimum value in the subtree of node (i) (including node (i) itself).## sample

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

1 1 4 2 1