Plum Blossom Placement

Fusu emerges from the cold winter of Meiling and finds himself at a rooted tree with \( n \) nodes. Recall that a tree is a simple connected graph with exactly \( n-1 \) edges. With node \( 1 \) designated as the root, the unique simple path from any node \( y \) to the root is well–defined.

For two directly connected nodes \( u \) and \( v \), we say that \( u \) is a child of \( v \) (and \( v \) is the parent of \( u \)) if \( u \) is not on the unique path from \( v \) to the root.

Fusu starts at node \( 1 \) and traverses the tree along its edges. At any node \( u \), his move is determined by the following rule: he either goes to one of \( u \)'s unvisited children or, if no such child exists, he returns to \( u \)'s parent.

Each node \( i \) is assigned a weight \( w_i \). Fusu’s goal is to place exactly \( w_i \) plum blossoms at node \( i \). However, there is a twist: he can only place the blossoms at a node \( u \) when all of its children have already been decorated with their required number of blossoms (i.e. each child \( v \) already has \( w_v \) blossoms). Moreover, at any moment Fusu may retrieve (collect) blossoms from any node without having to travel there.

This means Fusu can plan the order of decorating nodes arbitrarily as long as he follows his movement rules and the placement condition: when he is at node \( u \), if every child \( v \) of \( u \) already has its \( w_v \) blossoms, then he is permitted to place \( w_u \) blossoms at \( u \).

The key observation is that Fusu can traverse the tree in a depth–first fashion, decorating each subtree in turn and then recycling the blossoms collected from the decorated nodes to use elsewhere. Therefore, for any node, the minimum number of blossoms that Fusu must initially bring from Meiling is exactly the maximum blossom requirement along the unique DFS branch of that node’s subtree. In other words, if we define \( f(u) \) as the minimum number required to decorate the subtree rooted at \( u \), then

[ f(u) = \max\Bigl( w_u,\ \max_{v \text{ is a child of } u} f(v) \Bigr). ]

Your task is to compute, for each node \( i \) in the tree (where the tree is rooted at \( 1 \)), the minimal number \( f(i) \) such that Fusu can eventually decorate node \( i \) (and its subtree, if any) while following the given rules.

inputFormat

The first line contains an integer \( n \) denoting the number of nodes in the tree.

The second line contains \( n \) integers \( w_1, w_2, \ldots, w_n \), where \( w_i \) is the weight of node \( i \).

Each of the next \( n-1 \) lines contains two integers \( u \) and \( v \), representing an edge between nodes \( u \) and \( v \). It is guaranteed that the provided graph forms a tree, and node \( 1 \) is the root.

outputFormat

Output \( n \) integers separated by spaces. The \( i \)-th integer should be the minimum number of blossoms Fusu must bring from Meiling so that node \( i \) can be decorated with exactly \( w_i \) blossoms according to the rules.

sample

2
3 5
1 2

5 5