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=;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=*x+ch-'',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 = ;
struct Node{
int to,next;
}G[maxn<<];
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] <= ) inc[u] += -val[u];
else dec[u] += val[u];
return;
}
#undef v
int main(){
int n;read(n);
for(int i=,u,v;i<n;++i){
read(u);read(v);
add(u,v);add(v,u);
}for(int i=;i<=n;++i) read(val[i]);
dfs();
printf("%lld\n",inc[]+dec[]);
getchar();getchar();
return ;
}