Zero Tree

题意翻译

题目描述 一棵树是一个有n个节点与正好n-1条边的图；并且符合以下条件：对于任意两个节点之间有且只有一条简单路径。 我们定义树T的子树为一棵所有节点是树T节点的子集，所有边是T边的子集的树。 给定一颗有n个节点的树，假设它的节点被编号为1到n。每个节点有一个权值，$v_i$表示编号为i的节点的权值。你需要进行一些操作，每次操作符合以下规定： - 在给定的这棵树中选择一棵子树，并保证子树中含有节点1 - 把这棵子树中的所有节点加上或减去1 你需要计算至少需要多少次操作来让所有的节点的权值归零。 输入数据 第一行包含一个整数n，表示树中节点的数量 接下来的n-1行，一行两个整数u,v，表示u和v之间有一条边(u!=v)。 最后一行包含n个整数$v_i$，用空格隔开，表示每个节点的权值 输出数据 一行一个整数，输出最小需要的操作次数。 输入样例 ``` 3 1 2 1 3 1 -1 1 ``` 输出样例 ``` 3 ``` 数据规模 对于$30\%$的数据，$n\leq100,|vi|\leq1000$ 对于$50\%$的数据，$n\leq10^4$ 对于$100\%$的数据，$n\leq10^5,|vi|\leq10^9$ Translated by 首相大大

题目描述

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.

输入输出格式

输入格式

The first line of the input contains $ n $ ( $ 1<=n<=10^{5} $ ). 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}|<=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.

输入输出样例

输入样例 #1

3
1 2
1 3
1 -1 1

输出样例 #1

3