CodeForces

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

题目大意：
 给定你一颗树，每个点上有权值。
 现在你每次取出这颗树的一颗子树(即点集和边集均是原图的子集的连通图)且这颗树中必须包含节点1
 然后将这颗子树中的所有点的点权+1或-1
 求把所有点权全部变为0的最小次数(n<=10^5)

题解：

　　

因为每一次的子树中都必须有1，所以我们得知每一次变换的话1的权值都会变化

所以我们以1为根

现在，我们发现，如果一个节点的权值发生变化，那么他的父节点的权值一定发生变化

而一个点因为其子节点而导致的,不是用于平衡自己权值的变化是不可避免的

所以我们考虑最小化这个值，我们假设现在他的所有儿子都是叶子节点

那么节点u被变化的值即为inc[u] + dec[u]其中inc[u] = max{inc[v]},dec[u] = max{dec[v]}

inc[u]表示这个节点在最优情况下被加了多少次

dec[u]表示这个节点在最坏情况下被减了多少次

所以我们知道，在我们处理完了u的所有子树的问题后，就要解决自己本身的问题

所以这是根据val[u]的正负来调整inc,和dec

O(n)dfs即可

code

　　

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &x){
    x=0;char ch;bool flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
template<typename T>inline T cat_max(const T &a,const T &b){return a>b ? a:b;}
template<typename T>inline T cat_min(const T &a,const T &b){return a<b ? a:b;}
const int maxn = 100010;
struct Node{
    int to,next;
}G[maxn<<1];
int head[maxn],cnt;
void add(int u,int v){
    G[++cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt;
}
ll val[maxn],inc[maxn],dec[maxn];
int fa[maxn];
#define v G[i].to
void dfs(int u){
    for(int i = head[u];i;i=G[i].next){
        if(v == fa[u]) continue;
        fa[v] = u;
        dfs(v);
        inc[u] = cat_max(inc[u],inc[v]);
        dec[u] = cat_max(dec[u],dec[v]);
    }
    val[u] = val[u] + inc[u] - dec[u];
    if(val[u] <= 0) inc[u] += -val[u];
    else dec[u] += val[u];
    return;
}
#undef v
int main(){
    int n;read(n);
    for(int i=1,u,v;i<n;++i){
        read(u);read(v);
        add(u,v);add(v,u);
    }for(int i=1;i<=n;++i) read(val[i]);
    dfs(1);
    printf("%lld
",inc[1]+dec[1]);
    getchar();getchar();
    return 0;
}