一方通行を倒すため、御坂妹たちは団結することにした！彼女たちは学園都市の風力発電機のそばに陣取り、一方通行の能力を弱体化させようとしている。

学園都市には $n$ 個の風力発電機があり、御坂妹もちょうど $n$ 人いる。御坂ネットワークの接続関係は木構造をなしている。各風力発電機には電力 $w_i$ が設定されており、一方通行が $i$ 番目の御坂妹の場所に現れると、すべての御坂妹が彼に向かって能力を発動する。しかし、御坂妹の能力は団結して初めて発動するものであり、どの二人の御坂妹も互いに協力して一方通行に対する抵抗エネルギーを生み出す。一方通行がいる場所を根とみなしたとき、二人の妹 $u < v$ が協力して発動するエネルギーは $w_{\mathrm{lca}(u, v)}$ である。御坂ネットワークが発動する総エネルギーは、すべての妹のペアが発動するエネルギーの総和である。一方通行がそれぞれの位置にいる場合について、御坂ネットワークが発動する総エネルギーを計算せよ。

入力

1行目に正整数 $n$ が与えられる。これは風力発電機の数である。

続く1行に $n$ 個の正整数が与えられる。$i$ 番目の正整数 $w_i$ は $i$ 番目の風力発電機の電力を表す。

続く $n - 1$ 行の各行に、2つの正整数 $u, v$ ($1 \le u, v \le n$) が与えられる。これは $u$ と $v$ の間に道路があることを表す。

出力

1行に $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$

すべてのデータにおいて、$n \le 5\times 10^5, 0 \le w_i \le 10^6$ を満たす。