B - Zero Tree

题意：每次可以将包含1的节点的子树加1或者减1，问最小的操作数让整棵树变成0；
解题思路：
由于每次操作都要带上1，那么我们把1当做根节点，然后我们发现他的操作数与子树有关，先不考虑u这个节点，仅考虑他的子树，那么操作数有上升的也有下降的，那就是启发我们开两个数组，up，down记录上升的次数和下降的次数，状态方程转移：up[u]=max(up[j]),down[u]=max(down[j]),然后再考虑u这个点，先把down和up都计算到val中，如果val大于零down+=val，否则up-=val
最后把up和down加起来就是答案了。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=400010;
int n;
int idx;
int h[N];
int ne[N],e[N];
void add(int a,int b)
{
   
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int up[N];
int down[N];
int val[N];
void dfs(int u,int fa)
{
   
	int maxx=0,maxx2=0;
	for(int i=h[u];~i;i=ne[i])
	{
   
		int j=e[i];
		if(j==fa)	continue;
		dfs(j,u);
		maxx=max(maxx,up[j]);
		maxx2=max(maxx2,down[j]);
	}
	up[u]=maxx;
	down[u]=maxx2;
	val[u]+=up[u];
	val[u]-=down[u];
	if(val[u]<0)
	up[u]-=val[u];
	else
	down[u]+=val[u];
}
signed main()
{
   
	scanf("%lld",&n);
	memset(h,-1,sizeof h);
	for(int i=0;i<n-1;i++)
	{
   
		int a,b;
		scanf("%lld%lld",&a,&b);
		add(a,b),add(b,a);
		}	
	for(int i=1;i<=n;i++)
	scanf("%lld",&val[i]);
	dfs(1,-1);
	printf("%lld\n",up[1]+down[1]);
	return 0;
}