A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 不可言 中级黑马   /  2014-6-16 13:33  /  2014 人查看  /  3 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

发布公司: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

3 个回复

倒序浏览
支持支持!!
回复 使用道具 举报

版主早上好(第36个回复)
回复 使用道具 举报
多谢分享
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马