Description

In the year $3000$, the Earth Union has conquered $N$ planets in the Milky Way. For budget reasons, the government built only $N-1$ bidirectional spacetime tunnels between planets to ensure that any two planets are mutually reachable. For administrative reasons, the governor of the $i$-th planet requires that each citizen must not use spacetime tunnels to leave that planet more than $H_i$ times within a year (this is counted by the number of departures; if you have already departed from that planet $H_i$ times, then you cannot leave that planet via a spacetime tunnel again within the same year).

Louis Paosen is an interstellar traveler. He hopes to use spacetime tunnels as many times as possible, but he does not want to end up settling on a planet with overly harsh conditions. Therefore, he wants to know, for each planet $i$, if he starts from planet $0$ and finally ends his trip on planet $i$, what is the maximum number of spacetime tunnel uses possible along the journey.

Input Format

The input file galaxy.in contains an integer $N$ on the first line.
The second line contains $N$ integers $H_i$, representing the departure limit for each planet.
Each of the next $N-1$ lines contains two integers, indicating that there is a spacetime tunnel between these two planets.
Planets are numbered from $0$, and Louis Paosen starts on planet $0$.

Output Format

The output file is galaxy.out. It contains $N$ lines, each with one integer, where the integer on line $i$ is the maximum possible number of spacetime tunnel uses if the trip ends on planet $i$.

3
2 6 2
0 1
1 2

8
7
8

Hint

For $40\%$ of the testdata, $N \leq 500$.

For $100\%$ of the testdata, $N \leq 50000$.

All departure limits satisfy $1 \leq H_i \leq 40000$, and each planet’s $H_i$ is greater than or equal to the number of planets directly connected to it (i.e., its degree).

Translated by ChatGPT 5