AT_KeioPC2025_j Moving Pieces on Namori

给定一个有 $N$ 个顶点和 $N$ 条边的简单连通无向图，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。每个顶点上都放置有若干个棋子，顶点 $i$ 上有 $A_i$ 个棋子。 你可以进行以下操作，次数不限（可以为 $0$ 次）： - 从有至少 $1$ 个棋子的顶点 $x$ 和与其相邻的顶点 $y$ 中任选一对，将 $x$ 上的一个棋子移动到 $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$

输出所需的最小操作次数。

### 样例解释1 按以下顺序操作，可以用 $3$ 次操作达到目标： - 将顶点 $4$ 的一个棋子移动到顶点 $3$。 - 将顶点 $3$ 的一个棋子移动到顶点 $1$。 - 将顶点 $3$ 的一个棋子移动到顶点 $2$。 用 $2$ 次或更少操作无法达到目标，因此答案是 $3$。 ### 数据范围 - $3 \leq N \leq 3\times 10^5$ - $1 \leq u_i, v_i \leq N\quad (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$ - 所有输入均为整数 由 ChatGPT 5 翻译