当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3719：Art of Balance

题目描述

In the recent years, sculptor Clark's works rank highly by more and more connoisseurs. Among Clark's works, "Art of balance" is the most famous one. The skeleton of the work is a combination of scales, as shown in the figure below. Being reputed as the masterpiece of contemporary sculptor, “Art of balance” shows the weight and value of human behaviors and potential views on the spiritual level and display a magic balance of their relationships.

Unfortunately, due to some unexpected reasons, "Art of balance" was damaged in a fire disaster - the weights of these scales are all destroyed. In order to repair this treasure of art, some artists re-make these weights according to some existed records, but the scales cannot remain balance for some technical reasons and it needs some adjusting. Now you are asked to complete the job.

To simplify the problem, we consider the skeleton as a binary tree. The leaves of the tree are where we should add weights. It is guaranteed that number of leaves equals the number of weights, and only one weight can be added to a leaf node. The weights of these weights are already known and all weights have the same appearance. At the beginning, the fulcrum of each scale is always at the middle of the rod, and each rod has a fixed length of 1000. When these weights were arranged to leaf nodes, the fulcrum should be adjusted according to the rule of torque balance so that the scale can remain stable. For each scale, let adjusted distance be the length of the line segment between the original fulcrum (i.e. the middle point) and the adjusted fulcrum. Your job is to find such an arrangement that minimize the sum of each scale's adjusted distance.

输入解释
The first line contains an integer representing the number of test cases.
For each test case, the first line contains an integer representing the number of nodes N (3≤N≤100). Next N lines describe a tree. The nodes are numbered from 1 to N. If the ith node is not a leaf node, the ith line should contain two positive integers, which stand for the ID of ith node’s left child and the ID of ith node’s right child. Otherwise the ith node is a leaf node and the ith line should be "-1 -1". It is guaranteed that Node 1 will be the root of the tree. The following line contains an integer M representing the number of weights (2≤M≤16). Next line contains M positive integers standing for the value of these weights. The value of a single weight will not exceed 100.
输出解释
For each test case, output a real number representing the minimum value of the sum of the adjusted distance, rounded to 0.001.
输入样例 
3
3
2 3
-1 -1
-1 -1
2
1 2
7
2 3
4 5
6 7
-1 -1
-1 -1
-1 -1
-1 -1
4
2 2 3 3
9
2 3
4 5
-1 -1
6 7
-1 -1
8 9
-1 -1
-1 -1
-1 -1
5
8 4 2 1 1
输出样例 
166.667
100.000
0.000
提示

In sample 1, the adjusted distance is (2/3-1/2)*1000.
In sample 2, only the top scale is adjusted and the total adjusted distance is (6/10-1/2)*1000+0+0=100.
In sample 3, we have an arrangement that every scale can remain balance without any adjusting. So the sum of adjusted distance is 0.
Note that adjusting the fulcrum of a certain scale will not affect the other scales' balance and each rod has a fixed length of 1000.
该题目是Virtual Judge题目，来自 北京大学POJ
题目来源 POJ Monthly Contest – 2009.02.22, Mars
源链接： POJ-3719
最后修改于 2020-10-29T07:09:02+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
3000 65536