Maximizing Wormhole Usage in Interstellar Travel

In the year \(3000\), the Earth Federation has conquered \(N\) planets in the galaxy and has built exactly \(N-1\) bidirectional time‐tunnels so that any two planets are reachable from one another. In order to manage these planets, the governor of the \(i\)th planet imposes a restriction: in one year a citizen may not use the tunnels leaving planet \(i\) more than \(H_i\) times. Note that the counter is based on departures (if you have already departed from planet \(i\) exactly \(H_i\) times in that year, you cannot use any tunnel leaving \(i\) again during that year).

Louis Paosen, an interstellar traveler, wishes to take as many tunnel trips as possible, but he also wants to avoid ending his journey on a planet with an overly strict departure quota. Therefore, for every planet \(i\) he wonders: if he starts his journey at planet \(0\) and eventually ends at planet \(i\), what is the maximum number of tunnel passages he can take while obeying all the departure restrictions?

A key observation is that although the network is a tree, Louis is free to use cycles (i.e. he may traverse some tunnels more than once) as long as at every visit the departure from a planet does not exceed its quota.

Hint (with proof‐idea): One may show that if \(S=\sum_{j=0}^{N-1}H_j\) and \(d(0,i)\) is the distance (number of tunnels) in the simple path from planet \(0\) to planet \(i\), then the answer for planet \(i\) is always equal to

[ \text{Answer}_i = \left\lceil \frac{S+d(0,i)}{2} \right\rceil. ]

You are to compute and output these maximum numbers for all planets \(0\) to \(N-1\).

inputFormat

The first line contains an integer \(N\) (the number of planets).

The second line contains \(N\) integers \(H_0, H_1, \dots, H_{N-1}\) where \(H_i\) is the maximum number of times one may leave planet \(i\).

Each of the following \(N-1\) lines contains two integers \(u\) and \(v\) (\(0 \le u, v < N\)) indicating that there is a bidirectional time-tunnel between planets \(u\) and \(v\).

outputFormat

Output a single line containing \(N\) integers. The \(i\)th integer should be the maximum number of tunnels that can be used on a valid journey that starts at planet \(0\) and ends at planet \(i\).

sample

2
2 2
0 1

2 3