题目大意：

 给定你一颗树，每个点上有权值。

 现在你每次取出这颗树的一颗子树(即点集和边集均是原图的子集的连通图)且这颗树中必须包含节点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

　　

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 typedef long long ll; 6 template
        
         inline void read(T &x){ 7     x=0;char ch;bool flag = false; 8     while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; 9     while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;10 }11 template
         
          inline T cat_max(const T &a,const T &b){
   return a>b ? a:b;}12 template
          
           inline T cat_min(const T &a,const T &b){ return a