题目描述

一棵树是一个有 $n$ 个节点与正好 $n-1$ 条边的图；并且符合以下条件：对于任意两个节点之间有且只有一条简单路径。

我们定义树 $T$ 的子树为一棵所有节点是树 $T$ 节点的子集，所有边是 $T$ 边的子集的树。

给定一颗有 $n$ 个节点的树，假设它的节点被编号为 $1$ 到 $n$。每个节点有一个权值 $v_i$。你需要进行一些操作，每次操作符合以下规定：

• 在给定的这棵树中选择一棵子树，并保证子树中含有节点 $1$；
• 把这棵子树中的所有节点加上或减去 $1$。

你需要计算至少需要多少次操作来让所有的节点的权值归零。

输入格式

第一行包含一个整数 $n$，表示树中节点的数量，$1\le n\le 10^5$。

接下来的 $n-1$ 行，一行两个整数 $u,v$，表示 $u$ 和 $v$ 之间有一条边。

最后一行包含 $n$ 个整数 $v_i$，用空格隔开，表示每个节点的权值，$|v_i|\le 10^9$。

输出格式

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

3
1 2
1 3
1 -1 1

3