AT_KeioPC2025_j Moving Pieces on Namori

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点 $ N $ 辺の単純連結無向グラフが与えられます。 $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。 各頂点にはいくつかの駒が置かれており、頂点 $ i $ には $ A_i $ 個の駒が置かれています。 あなたは以下の操作を $ 0 $ 回以上行うことができます。 - 駒が $ 1 $ つ以上置かれている頂点 $ x $ と、 $ x $ に隣接する頂点 $ y $ を任意に選ぶ。 $ x $ に置かれている駒を $ 1 $ つ $ y $ に移動させる。 あなたの目標は、頂点 $ i (i = 1, 2, \ldots, N) $ に駒が $ B_i $ 個置かれている状態にすることです。目標の達成に必要な操作回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ u_1 $ $ v_1 $ $ \vdots $ $ u_N $ $ v_N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_N $

答えを出力せよ。

### Sample Explanation 1 以下のような順で操作を行うと $ 3 $ 回の操作で目標を達成できます。 - 頂点 $ 4 $ の駒を $ 1 $ つ頂点 $ 3 $ に移動させる。 - 頂点 $ 3 $ の駒を $ 1 $ つ頂点 $ 1 $ に移動させる。 - 頂点 $ 3 $ の駒を $ 1 $ つ頂点 $ 2 $ に移動させる。 $ 2 $ 回以下の操作では目標を達成できないため、答えは $ 3 $ です。 ### Constraints - $ 3\leq N\leq 3\times 10^5 $ - $ 1\leq u_i, v_i \leq N $ $ (i = 1, 2, \ldots, N) $ - 与えられるグラフは単純かつ連結 - $ 0\leq A_i, B_i \leq 10^6 $ - $ \sum_{i = 1}^N A_i = \sum_{i = 1}^N B_i $ - 入力はすべて整数