← 返回题目列表

Codeforces · 274/B

B. 零树

中文机器翻译题面 查看原题

树是具有 n 个顶点和恰好 n - 1 条边的图;该图应满足以下条件:其任意一对顶点之间恰好存在一条最短(按边数)路径。

树 T 的子树是一棵树,其顶点和边都是 T 的顶点和边的子集。

给你一棵有 n 个顶点的树。考虑其顶点编号为 1 到 n 的整数。此外,该树的每个顶点上都写有一个整数。最初写在第 i 个顶点上的整数等于 vi。您可以一次性应用以下操作:

1. 选择给定树中包含编号为 1 的顶点的子树。
2. 将写入该子树顶点的所有整数增加(或减少)1。

计算使给定树的顶点上写入的所有整数等于零所需的最小移动次数。

输入

输入的第一行包含 n (1 ≤ n ≤ 105)。接下来的 n - 1 行中的每一行都包含两个整数 ai 和 bi (1 ≤ ai, bi ≤ n; ai ≠ bi),表示顶点 ai 和 bi 之间有一条边。保证输入图是一棵树。

输入的最后一行包含 n 个空格分隔的整数 v1, v2, ..., vn (|vi| ≤ 109) 的列表。

输出

打印解决任务所需的最少操作数。

请不要编写 %lld 说明符来读取或写入 С++ 中的 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

3
1 2
1 3
1 -1 1

输出 #1

3