为了打败一方通行，御坂的妹妹们将要联合起来！她们将会把守在学园都市的风力发电机旁，以将一方通行的能力削弱！

学院都市有 $n$ 个风力发电机，而御坂的妹妹恰好也有 $n$ 个，御坂网络的连接方法是一颗树。每个风力发电机有一个功率 $w_i$ ，当一方通行在第 $i$ 个御坂妹妹的地方出现时，所有的御坂都会朝向他发动能力。但御坂妹妹的能力是联合起来才能发动的，每个御坂和另一个御坂都会联合起来产生抵抗一方通行的能量。如果将一方通行所在的位置视为根，则一对姐妹 $u < v$ 联合起来发动的能量是 $w_{\mathrm{lca}(u, v)}$ 。御坂网络发动的总能量就是每一对姐妹的发动能量之和。你要求的就是对于一方通行所在的每一个位置，计算出御坂网络发动的总能量。

输入格式

一行一个正整数 $n$ 表示风力发电机数量。

接下来一行共 $n$ 个正整数，第 $i$ 个正整数 $w_i$ 表示第 $i$ 个风力发动机的功率。

接下来 $n - 1$ 行每行两个正整数 $u\ v$ 其中 $1 \le u, v \le n$ 表示 $u$ 到 $v$ 有一条道路。

输出格式

输出一行共 $n$ 个整数，第 $i$ 个表示如果一方通行在 $i$ 位置，御坂们联合发出的能量。

样例数据

样例 1 输入

3
2 5 7
3 2
1 2

样例 1 输出

9 15 19

子任务

对于测试点1-4： $n \le 50$

对于测试点5-8：$n\le500$

对于测试点9-12：$n\le2000$

对于测试点13-14：$n\le5\times 10^4$，树是一颗二叉树

对于测试点15-16：$n\le5\times 10^4$，树是一条链

对于测试点17-18：$n\le 5\times 10^4$

对于测试点19-20：$n\le 5\times 10^5$，树是一条链

对于测试点21-22：$ n\le 5\times 10^5$，树是一颗菊花

对于测试点23-25：$n\le 5\times 10^5$

对于 $100\%$ 的数据，保证 $n \le 5\times 10^5, 0 \le w_i \le 10^6$