本文主要是介绍51 nod 1424，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1424 零树
有一棵以1为根的树，他有n个结点，用1到n编号。第i号点有一个值vi。
现在可以对树进行如下操作：
步骤1：在树中选一个连通块，这个连通块必须包含1这个结点。
步骤2：然后对这个连通块中所有结点的值加1或者减1。
问最少要经过几次操作才能把树中所有结点都变成0。
注意：步骤1与步骤2合在一起为一次操作。
Input
单组测试数据。
第一行有一个整数n(1 ≤ n ≤ 10^5)
接下来n-1行，每行给出 ai 和 bi (1 ≤ ai, bi ≤ n; ai ≠ bi)，表示ai和bi之间有一条边，输入保证是一棵树。
最后一行有n个以空格分开的整数，表示n个结点的值v1, v2, ..., vn (|vi| ≤ 10^9)。
Output
输出一个整数表示最少的操作步数。.
Input示例
3
1 2
1 3
1 -1 1
Output示例
3
System Message (题目提供者)
C++的运行时限为：1000 ms ，空间限制为：131072 KB
题解：对于树来说，任意一个节点如果与根节点联通，那么其祖先一定和根节点联通。所以对于任意一颗子树，up【i】表示以i为根的子树最少+1的次数，down【i】表示i为根的子树最少-1的次数，每次取儿子节点中最大的即可。#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define N 300000
using namespace std;
int n;
int last[N<<1],to[N<<1],head[N],cnt=0;
void ins(int u,int v){last[++cnt]=head[u];head[u]=cnt;to[cnt]=v;
}
long long down[N],up[N],val[N];
void dfs(int x,int fa)
{for(int i=head[x];i;i=last[i]){if(to[i]==fa) continue;dfs(to[i],x);down[x]=max(down[x],down[to[i]]);up[x]=max(up[x],up[to[i]]);}val[x]+=(up[x]-down[x]);if(val[x]>0) down[x]+=val[x];if(val[x]<0) up[x]-=val[x];return ;
}
int main()
{int u,v;scanf("%d",&n);for(int i=1;i<n;i++){scanf("%d%d",&u,&v);ins(u,v);ins(v,u);}for(int i=1;i<=n;i++) scanf("%lld",&val[i]);dfs(1,0);printf("%lld",(up[1]+down[1]));return 0;
}
这篇关于51 nod 1424的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
