問題文

$N$ 頂点の木があり， $i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ をつないでいます。
あなたは，この木から0個以上の頂点を消すことができます。消す頂点の選び方は $2^N$ 通り存在しますが，それぞれの選び方について，スコアが以下の規則に従って定義されます。

• スコアを $0$ で初期化する。
• $1$ 以上 $N$ 以下のすべての整数 $i$ について，以下を行う。
• 頂点 $i$ が消されている場合，スコアに $a_i$ を加算する。
• 頂点 $i$ が消されずに残っている場合，頂点 $i$ に隣接しかつ消されずに残っている頂点の数を $d_i$ としたとき，スコアに $d_i\times b_i$ を加算する。

入力

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

• 入力はすべて整数
• $1\le N\le 10^5$
• $-10^9 \le a_i \le 10^9$
• $-10^9 \le b_i \le 10^9$
• $1\le u_i, v_i\le N$
• 与えられるグラフは木である

出力

得られるスコアの最大値を1行に出力してください。

サンプル

サンプル1

入力

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

出力

17

頂点4のみを消し，頂点1, 2, 3を残します。このとき，

• 頂点1について：頂点1は残っており，$d_1=2$（頂点2, 3）なので，スコアに $2\times b_1=10$ を加算します。
• 頂点2について：頂点2は残っており，$d_2=1$（頂点1）なので，スコアに $1\times b_2=-1$ を加算します。
• 頂点3について：頂点3は残っており，$d_3=1$（頂点1）なので，スコアに $1\times b_3=0$ を加算します。
• 頂点4について：頂点4は消されたので，スコアに $a_4=8$ を加算します。

より，この消し方のスコアは17です。他の頂点の消し方でこのスコアを超えることはできず，これが最大値です。

2
-40 -20
-10 -30
2 1

-20

1
-1000000000
1000000000

0

7
-521286975 241394095 679500630 908939842 -663879330 -918836774 -200080451
-521243563 425878585 50490545 924277174 963020278 437158704 866091708
1 2
1 3
2 4
2 5
3 6
3 7

3621999149