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
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.
Output
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 1166.667
100.000
0.000Hint
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
POJ Monthly Contest – 2009.02.22, Mars