為了打敗一方通行，御坂妹妹們將要聯合起來！她們將會把守在學園都市的風力發電機旁，以將一方通行的能力削弱！

學園都市有 $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 \le 500$

對於測試點 9-12： $n \le 2000$

對於測試點 13-14： $n \le 5\times 10^4$，樹是一棵二叉樹

對於測試點 15-16： $n \le 5\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$