問題文

すぬけくんは $N$ 頂点の木の記録を古代遺跡で見つけました。 すぬけくんはこの記録から分かったことを以下にまとめました。

• この木の頂点には $1,2,...,N$ の番号が、辺には $1,2,...,N-1$ の番号がついていた
• 辺 $i$ は頂点 $a_i$ と $b_i$ を双方向につないでいた
• それぞれの辺の長さは $1$ 以上 $10^{18}$ 以下の整数であった
• 頂点 $i$ から頂点 $1,...,N$ への最短距離の和が $s_i$ であった

これらの情報から、それぞれの辺の長さを復元してください。 なお、与えられる記録において、これらの情報と矛盾しないように辺の長さを定めることが可能なことが保証されます。 さらに、そのような場合においてそれぞれの辺の長さが一意に定まることが証明できます。

制約

• $2 \\leq N \\leq 10^{5}$
• $1 \\leq a_i,b_i \\leq N$
• $1 \\leq s_i \\leq 10^{18}$
• 与えられるグラフは木
• 与えられる入力は全て整数
• 与えられる情報から辺の長さは復元可能である
• それぞれの辺の長さは $1$ 以上 $10^{18}$ 以下の整数となる

部分点

• $300$ 点分のデータセットでは $a_i = i,b_i = i+1$ が成立する
• 別の $200$ 点分のデータセットでは $N \\geq 3, a_i = 1,b_i = i+1$ が成立する

入力

入力は以下の形式で標準入力から与えられる。

$N$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $s_1$ $s_2$ $...$ $s_{N}$

出力

答えを $N-1$ 行に出力せよ。$i$ 行目には辺 $i$ の長さを出力せよ。

入力例 1

4
1 2
2 3
3 4
8 6 6 8

出力例 1

1
2
1

• 与えられるのは以下の図のような木の記録です

入力例 2

5
1 2
1 3
1 4
1 5
10 13 16 19 22

出力例 2

1
2
3
4

• 与えられるのは以下の図のような木の記録です

入力例 3

15
9 10
9 15
15 4
4 13
13 2
13 11
2 14
13 6
11 1
1 12
12 3
12 7
2 5
14 8
1154 890 2240 883 2047 2076 1590 1104 1726 1791 1091 1226 841 1000 901

出力例 3

5
75
2
6
7
50
10
95
9
8
78
28
89
8