配点 : 100 点
問題文
在顶部 编号为 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 。找出实现目标所需的最少操作次数。
制約
- 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
- 输入都是整数
入力
输入是按以下格式从标准输入给出的。
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
4 1 2 2 3 3 1 4 3 3 1 3 4 4 2 2 3
出力例 1
3
如果按以下顺序执行操作, 您可以通过 3 步实现您的目标。
- 頂点 4 片 1 一个顶点 由于少于 3 。
- 頂点 3 片 1 一个顶点 由于少于 1 。
- 頂点 3 片 1 一个顶点 由于少于 2 。
2 的操作无法实现目标,所以答案是 3 。
入力例 2
9 1 3 1 9 2 6 8 7 9 2 1 5 8 2 2 3 1 4 9 9 8 2 4 4 3 5 3 3 5 3 4 4 2 8 9 9
出力例 2
29