F: ボタンの木

問題文

$N$ 頂点 $N-1$ 辺からなる木があり、$i$ 番目の辺は $u_i$ 番目の頂点と $v_i$ 番目の頂点を接続しています。

各頂点にはボタンが咲いており、$i$ 番目の頂点に咲いているボタンをボタン $i$ と呼ぶことにします。

はじめ、ボタン $i$ の美しさは $a_i$ です。

ボタン $i$ を押すたびに、ボタン $i$ の美しさを隣接するボタンに $1$ ずつ分け与えます。

すなわち、$i$ 番目の頂点に $c_1, ..., c_k$ 番目の頂点が隣接している場合、ボタン $i$ の美しさが $k$ 減少し、ボタン $c_1, ..., c_k$ の美しさがそれぞれ $1$ ずつ増加します。

このとき、負の美しさのボタンを押しても良いし、ボタンを押した結果あるボタンの美しさが負になっても良いです。

あなたの目的はボタン $1, 2, ..., N$ の美しさをそれぞれ $b_1, ..., b_N$ にすることです。

最小で合計何回ボタンを押せば目的を達成できるでしょうか。

制約

  • 入力はすべて整数である
  • $1 \leq N \leq 10^5$
  • $1 \leq u_i, v_i \leq N$
  • $-1000 \leq a_i, b_i \leq 1000$
  • $\sum_i a_i = \sum_i b_i$
  • 与えられるグラフは木である
  • 与えられる入力において目的は必ず達成できる

入力

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

$N$
$u_1$ $v_1$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$a_1$ $a_2$ $...$ $a_N$
$b_1$ $b_2$ $...$ $b_N$

出力

目的を達成するためにボタンを押す合計回数の最小値を出力せよ。

入力例1

4
1 2
1 3
3 4
0 3 2 0
-3 4 5 -1

出力例1

4

次のように合計 $4$ 回ボタンを押すことで目的を達成でき、このときが最小です。

  • ボタン $1$ を $2$ 回押します。ボタン $1, 2, 3, 4$ の美しさがそれぞれ $-4, 5, 4, 0$ に変化します。
  • ボタン $2$ を $1$ 回押します。美しさがそれぞれ $-3, 4, 4, 0$ に変化します。
  • ボタン $4$ を $1$ 回押します。美しさがそれぞれ $-3, 4, 5, -1$ に変化します。

入力例2

5
1 2
1 3
3 4
3 5
-9 5 7 1 8
-7 4 5 1 9

出力例2

3