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

Time Limit: 2 Sec Memory Limit: 256 MB

Description

A tree is a graph with nn 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 TT is a tree with both vertices and edges as subsets of vertices and edges of TT.

You are given a tree with nn vertices. Consider its vertices numbered with integers from 11 to nn. Additionally an integer is written on every vertex of this tree. Initially the integer written on the ii-th vertex is equal to viv_i. In one move you can apply the following operation:

  1. Select the subtree of the given tree that includes the vertex with number 11.
  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 nn (1n1051 \leqslant n \leqslant 10^5). Each of the next n - 1 lines contains two integers aia_i and bib_i (1ai,bin1 \leqslant a_i, b_i \leqslant n; aibia_i \neq b_i) indicating there is an edge between vertices aia_i and bib_i. It is guaranteed that the input graph is a tree.

The last line of the input contains a list of nn space-separated integers v1,v2,vnv_1, v_2, \cdots v_n (vi109|v_i| \leqslant 10^9).

Output

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

Sample Input

1
2
3
4
3
1 2
1 3
1 -1 1

Sample Output

1
3

Solution

思路分析:

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

树形 DP:

  • up(i)up(i) 表示根节点为 vv 的子树要变成 00,最少被加上几次;down(v)down(v) 表示最少被减去几次。
  • up(i)=max{up(j)},down(i)=max{down(j)}\displaystyle up(i) = \max\{up(j)\}, down(i) = \max\{down(j)\},其中 jchild(i)j \in child(i)
  • 但如果 val(i)+up(i)down(i)val(i) + up(i) - down(i) 不为 00,那么还需要额外处理根节点 ii
  • 不妨设 11 为整棵树的根节点,则答案为 up(1)+down(1)up(1) + down(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
int n;
ll up[maxn], down[maxn], val[maxn];
vector<int> G[maxn];

void dfs(int v, int f) {
for (int u : G[v]) {
if (u != f) {
dfs(u, v);
up[v] = max(up[v], up[u]);
down[v] = max(down[v], down[u]);
}
}
val[v] += up[v] - down[v];
if (val[v] > 0) {
down[v] += val[v];
} else if (val[v] < 0) {
up[v] -= val[v];
}
}

int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
scanf("%lld", &val[i]);
}
dfs(1, 1);
printf("%lld\n", up[1] + down[1]);
return 0;
}