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