Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Art of Balance
Description 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. Input 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 i^{th} node is not a leaf node, the i^{th} line should contain two positive integers, which stand for the ID of i^{th} node’s left child and the ID of i^{th} node’s right child. Otherwise the i^{th} node is a leaf node and the i^{th} 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. Output For each test case, output a real number representing the minimum value of the sum of the adjusted distance, rounded to 0.001. Sample Input 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 Sample Output 166.667 100.000 0.000 Hint 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. Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator