CF274B.Zero Tree

A tree is a graph with n vertices and exactly n - 1 edges; this graph should meet the following condition: there exists exactly one shortest (by number of edges) path between any pair of its vertices.

A subtree of a tree T is a tree with both vertices and edges as subsets of vertices and edges of T.

You're given a tree with n vertices. Consider its vertices numbered with integers from 1 to n. Additionally an integer is written on every vertex of this tree. Initially the integer written on the i-th vertex is equal to v__i. In one move you can apply the following operation:

1. Select the subtree of the given tree that includes the vertex with number 1.
2. Increase (or decrease) by one all the integers which are written on the vertices of that subtree.

Calculate the minimum number of moves that is required to make all the integers written on the vertices of the given tree equal to zero.

树是包含 $n$ 个顶点和恰好 $n-1$ 条边的图；该图需满足如下条件：其任意两个顶点之间均存在唯一一条最短路径（以边数计）。

树 $T$ 的子树是指一个树，其顶点集与边集均为 $T$ 的顶点集与边集的子集。

给定一棵含 $n$ 个顶点的树。设该树的顶点编号为 $1$ 至 $n$ 的整数。此外，该树的每个顶点上均写有一个整数。初始时，第 $i$ 个顶点上所写的整数为 $v_i$。每次操作可执行以下步骤：

1. 选择给定树的一个子树，该子树必须包含编号为 $1$ 的顶点；
2. 将该子树中所有顶点上所写的整数同时加 $1$（或减 $1$）。

求使树中所有顶点上所写的整数均变为 $0$ 所需的最少操作次数。

The first line of the input contains n (1 ≤ n ≤ 105). Each of the next n - 1 lines contains two integers a__i and b__i (1 ≤ a__i, b__i ≤ n; a__i ≠ b__i) indicating there's an edge between vertices a__i and b__i. It's guaranteed that the input graph is a tree.

The last line of the input contains a list of n space-separated integers _v_1, _v_2, ..., v__n (|v__i| ≤ 109).

输入的第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）。接下来的 $n-1$ 行中，每行包含两个整数 $a_i$ 和 $b_i$（$1 \leq a_i, b_i \leq n$；$a_i \neq b_i$），表示顶点 $a_i$ 与 $b_i$ 之间存在一条边。保证输入的图是一棵树。

输入的最后一行包含 $n$ 个用空格分隔的整数 $v_1,\ v_2,\ \dots,\ v_n$（$|v_i| \leq 10^9$）。

Print the minimum number of operations needed to solve the task.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输出解决该任务所需的最少操作次数。

请注意，在 C++ 中读取或写入 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。