题意：每次可以将包含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; }