「Codeforces 275D」Zero Tree【树形 DP】

Time Limit: 2 Sec Memory Limit: 256 MB

Description

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 are 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.

Input

The first line of the input contains $n$ ($1 \leqslant n \leqslant 10^5$). Each of the next n - 1 lines contains two integers $a_i$ and $b_i$ ($1 \leqslant a_i, b_i \leqslant n$; $a_i \neq b_i$) indicating there is an edge between vertices $a_i$ and $b_i$. It is 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, \cdots v_n$ ($|v_i| \leqslant 10^9$).

Output

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

Solution

• 如果修改节点 $i$ 的权值，那么必定修改 $i$ 的父节点的权值 (根节点除外)。
• 对于每一颗子树而言，其根节点最少被加上其子节点中权值最小的值的绝对值，最少被减去其子节点中的最大值。

• $up(i)$ 表示根节点为 $v$ 的子树要变成 $0$，最少被加上几次；$down(v)$ 表示最少被减去几次。
• $\displaystyle up(i) = \max\{up(j)\}, down(i) = \max\{down(j)\}$，其中 $j \in child(i)$
• 但如果 $val(i) + up(i) - down(i)$ 不为 $0$，那么还需要额外处理根节点 $i$
• 不妨设 $1$ 为整棵树的根节点，则答案为 $up(1) + down(1)$