Time Limit: 2 Sec Memory Limit: 256 MB
A tree is a graph with 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 is a tree with both vertices and edges as subsets of vertices and edges of .
You are given a tree with vertices. Consider its vertices numbered with integers from to . Additionally an integer is written on every vertex of this tree. Initially the integer written on the -th vertex is equal to . In one move you can apply the following operation:
- Select the subtree of the given tree that includes the vertex with number .
- 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 (). Each of the next n - 1 lines contains two integers and (; ) indicating there is an edge between vertices and . It is guaranteed that the input graph is a tree.
The last line of the input contains a list of space-separated integers ().
Print the minimum number of operations needed to solve the task.
- 如果修改节点 的权值，那么必定修改 的父节点的权值 (根节点除外)。
- 设 表示根节点为 的子树要变成 ，最少被加上几次； 表示最少被减去几次。
- 则 ，其中 。
- 但如果 不为 ，那么还需要额外处理根节点 。
- 不妨设 为整棵树的根节点，则答案为 。