51nod-1424 零树

有一棵以1为根的树，他有n个结点，用1到n编号。第i号点有一个值vi。

现在可以对树进行如下操作：

步骤1：在树中选一个连通块，这个连通块必须包含1这个结点。

步骤2：然后对这个连通块中所有结点的值加1或者减1。

问最少要经过几次操作才能把树中所有结点都变成0。

注意：步骤1与步骤2合在一起为一次操作。

Input单组测试数据。
第一行有一个整数n(1 ≤ n ≤ 10^5)
接下来n-1行，每行给出 ai 和 bi (1 ≤ ai, bi ≤ n; ai ≠ bi)，表示ai和bi之间有一条边，输入保证是一棵树。
最后一行有n个以空格分开的整数，表示n个结点的值v1, v2, ..., vn (|vi| ≤ 10^9)。Output输出一个整数表示最少的操作步数。.Sample Input

3
1 2
1 3
1 -1 1

Sample Output

3

学习了一下树形动态规划，就是动态规划思想换到树上了，每个结点受左右子树的影响，为了方便记录，数据量大，所以用邻接表。
代码：

#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <cmath>
#include <cstring>
#define Max 100001
using namespace std;
int n,a,b;
int fir[Max * 2],nex[Max * 2],u[Max * 2],v[Max * 2],vis[Max];
long long up[Max],down[Max],val[Max];///up记录需要加多少1，down记录需要减多少1，val记录结点的值
void dfs(int d)
{
    vis[d] = 1;///记录访问过，不会反过来遍历
    int k = fir[d];
    while(k != -1)
    {
        if(vis[v[k]] != 1)
        {
            dfs(v[k]);
            up[d] = max(up[d],up[v[k]]);
            down[d] = max(down[d],down[v[k]]);
        }
        k = nex[k];
    }
    val[d] += up[d] - down[d];///完成左右子树的归0后，该结点的值发生变化
    if(val[d] > 0)down[d] += val[d];
    if(val[d] < 0)up[d] -= val[d];
}
int main()
{
    scanf("%d",&n);
    memset(fir,-1,sizeof(fir));
    for(int i = 0;i < n - 1;i ++)
    {
        scanf("%d%d",&u[i],&v[i]);
        nex[i] = fir[u[i]];
        fir[u[i]] = i;
        u[i + n - 1] = v[i];
        v[i + n - 1] = u[i];
        nex[i + n - 1] = fir[u[i + n - 1]];
        fir[u[i + n - 1]] = i + n - 1;
    }
    for(int i = 1;i <= n;i ++)
        scanf("%lld",&val[i]);
    dfs(1);
    printf("%lld",up[1] + down[1]);
}