黑马程序员技术交流社区

标题: 砍树 [打印本页]

---

作者: 不可言    时间: 2014-6-16 13:33
标题: 砍树
发布公司：CSDN
有 效 期：2014-05-15至2015-05-15
难 度 等 级：
答 题 时 长：120分钟
编程语言要求：C C++ Java C#

题目详情
图论中的树，是无向无环连通图。n个节点的树，有(n-1)条边。给定一棵树，每个节点都有一个权值。我们允许从这棵树中删掉一条边，把这棵树分成两棵树。每棵小树各自包含的节点的权值和定义为其自身的权值，我们的目标是，使得这两棵小树的权值差距尽可能小。（权值差的绝对值尽可能小。）
输入格式
多组数据，每组数据第一行是一个正整数n，表示树节点的个数（2<=n<=100000)。
第二行是n个空格分隔的正整数，表示每个节点的权值，该值不超过1000。
接下来有(n-1)行，每行有两个从1-n之间的整数，表示树的边。
输出格式
每组数据输出一行，表示最小的差距。


答题说明
输入样例  
2
1 2
2 1
输出样例  
1

原文链接：http://hero.csdn.net/Question/Details?ID=593&ExamID=588&from=4

---

作者: 傘が咲く    时间: 2014-6-17 08:19
支持支持！！

---

作者: 不可言    时间: 2014-6-17 10:04

傘が咲く 发表于 2014-6-17 08:19
支持支持！！

版主早上好（第36个回复）

---

作者: baby14    时间: 2018-9-11 08:05
多谢分享

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2