| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1154
Weight loss plan
Time Limit: 10000ms
Memory Limit: 65536kb Description
Fuch thinks himself a tree with n nodes. Spring is coming, so he is starting to lose weight. As a computer science student, Fuch is making the weight loss plan in a mathematical way.Fuch will reduce himself to a subtree with exactly m nodes and cut off all the other ones. He won't tear himself up, right? Two values, fatness and energy, are assigned to each node. To ensure that Fuch won't be too weak after losing weight as well as the efficiency of weight loss, the ratio of fatness' sum to energy's sum should be minimized. Fuch is so busy in losing weight, would you write a program for him? Input
Input consists of multiple test cases.For each test case, the first line contains two integers n and m, which are described above. (1<=m<=n<=1000) The next n lines each contains two positive integers fi and ei, indicating the fatness and energy of ith node. (1<=fi, ei<=1000000) The last n-1 lines each contains two integers ui and vi, indicating there's an edge between node ui and node vi. All nodes are numbered from 1 to n. A test case with n=m=0 indicates the end of input. Don't process this test case. Output
For each test case, output the minimum ratio in a single line. Round the answer to 0.0001.
Sample Input
5 3 1 2 2 3 3 4 4 5 5 6 1 2 1 3 1 4 1 5 0 0 Sample Output
0.6667 Source
fuch@USTC
|