题目描述

公元 3000 年，地球联盟已经攻占了银河系内的 $N$ 个星球，出于资金的考虑，政府仅仅在星球间建立了 $N-1$ 条双向时空隧道保证任意两个星球之间互相可达。出于管理上的考虑，第 $i$ 个星球的行政长官要求每个公民在一年内不得从该星球利用时空隧道次数超过 $H_i$ 次（这一统计是基于离开次数统计的，如果你已经使用从该星球离开过 $H_i$ 次，那么这一年内你就不能再使用时空隧道离开这个星球了）。Louis Paosen 是一个星际旅行家，他希望能使用尽量多次的时空隧道，但又不希望最终被迫定居的星球条件太过恶劣。所以他希望能知道对于每个星球 $i$，若从 $0$ 号星球出发，最终以 $i$ 号星球为终点，这样的星际旅行途中最多可以使用多少次时空隧道。

输入格式

输入文件 galaxy.in（洛谷中无需使用文件输入输出）的第一行包含一个整数 $N$。接下来的一行包含 $N$ 个整数 $H_i$，分别表示每个星球的离开次数限制。接下来 $N-1$ 行每行两个整数，表示这两个星球之间有时空隧道连接。星球的编号从 $0$ 开始，Louis Paosen 一开始在 $0$ 号星球。

输出格式

输出文件为 galaxy.out。文件包含 $N$ 行，每行一个整数，表示如果最终旅行结束在这个星球，最多可以使用时空隧道的次数。

3
2 6 2
0 1
1 2

8
7
8

提示

对于 $40 \%$ 的数据，$1\leq N \leq 500$

对于 $100 \%$ 的数据，$1\leq N \leq 50000$，$1 \leq H_i \leq 40000$，且每个星球的 $H_i$ 大于等于与该星球直接相连的星球数（即度数）。