Codeforces Round #168 (Div. 1) B. Zero Tree 树形DP

链接：

http://codeforces.com/contest/274/problem/B

题意：

给出一棵树，每个点有权值，每次操作可以对一个联通子集中的点全部加1，或者全部减1，且每次操作必须包含点1，问最少通过多少次操作可以让整棵树每个点的权值变为0.

题解：

定义状态up[u],down[u]代表点u被加操作的次数和点u被减操作的次数

因为必须包含点1，所以我们将树的根定在点1，那么对于每一点的子树中点，如果要修改的话，那么一定会经过当前这个点，因为这是通向根的必经之路。

所以对于每个点u,它被加修改和减修改的次数，就是它的儿子中进行该操作的最大次数，因为如果有两个儿子都需要进行该操作，那么完全可以两步并一步，所以只需要取最大值就可以了。

那么也就是up[u]=maxv adjacent to uup[v]

down[u]同理。

因为每次修改一定会修改点1，所以最后答案就是up[1]+down[1]

代码：

31 int n;
32 VI G[MAXN];
33 ll a[MAXN];
34 ll up[MAXN], down[MAXN];
35 
36 void dfs(int u, int par) {
37     rep(i, 0, G[u].size()) {
38         int v = G[u][i];
39         if (v == par) continue;
40         dfs(v, u);
41         up[u] = max(up[u], up[v]);
42         down[u] = max(down[u], down[v]);
43     }
44     a[u] += up[u] - down[u];
45     if (a[u] > 0) down[u] += a[u];
46     else up[u] -= a[u];
47 }
48 
49 int main() {
50     ios::sync_with_stdio(false), cin.tie(0);
51     cin >> n;
52     rep(i, 1, n) {
53         int u, v;
54         cin >> u >> v;
55         G[u].pb(v);
56         G[v].pb(u);
57     }
58     rep(i, 1, n + 1) cin >> a[i];
59     dfs(1, -1);
60     cout << up[1]+down[1] << endl;
61     return 0;
62 }