树是具有 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