Problem:


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



Sample input:
4
1 2
1 3
3 4
0 3 2 0
-3 4 5 -1


Sample output:
4

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    f = [0]*n
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a] += 1
        f[b] += 1
    a = LI()
    b = LI()
    c = [b[i]-a[i] for i in range(n)]
    d = [0]*n
    d[0] = 1
    q = deque([0])
    while q:
        x = q.popleft()
        nd = d[x] + 1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                q.append(y)
    V = list(range(n))
    V.sort(key = lambda x:-d[x])
    s = [1]*n
    for x in V:
        for y in v[x]:
            if d[y] < d[x]:
                s[y] += s[x]
    V = list(range(n))
    V.sort(key = lambda x:s[x])
    ans = 0
    for x in V:
        m = 0
        for y in v[x]:
            if s[y] < s[x]:
                if m < c[y]:
                    m = c[y]
        ans += m
        c[x] += m*f[x]
        for y in v[x]:
            if s[y] < s[x]:
                if c[y] < m:
                    res = m-c[y]
                    ans += res*s[y]
                    c[x] -= res
            else:
                c[y] -= m
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()