A biologist, Dr. Hsieh, currently aims at analyzing the ancestor-descendent relation between n species connected by an evolution tree T. Each species v of T is associated with a value-weight pair [valv, wv], where value valv is an integer between 0 and 10000, and weight wv is a non-negative integer between 1 and 10000. The density of T, denoted by d(T), is defined as ⌊ (Σv∈V(T)valv) / (Σv∈V(T)wv) ⌋. The weight-sum of T, denoted by w(T), is Σv∈V(T)wv. Dr. Hsieh’s research demonstrates that those species form a maximum-density path in T , under some weight constraint and the length constraint, diverge from a common ancestor. Furthermore, he formally formulates the above problem as follows: Given an evolution tree T = (V, E) of n specifies associated with value-weight pairs and wmin, wmax, and lmin, the goal is to compute the density of a maximum-density path P in T such that wmin ≤ w(P) ≤ wmax and lmin ≤ l(P), where l(P) is the number of edges contained in the path P.
Assume that T has 2 ≤ |V| ≤ 10000 species represented by {1, 2, . . . , |V|}, where 1 ≤ wmin ≤ 10000, 1 ≤ wmax ≤ 10000, and 0 ≤ lmin ≤ 9999. You are asked to write a program to compute the density of a maximum-density path of T , under both the weight and length constraints. If such a path does not exist, your program needs to output -1.
The input consists of a number of test cases. Each test case consists of one tree, which has the following format: The first line contains one positive integer 2 ≤ n ≤ 10000, which is the number of species of the input tree. The second line contains three numbers, wmin , wmax , lmin , in which any consecutive numbers are separated by a single space. The next n lines contain n species such that one line contains one specifies and the corresponding value and weight. Each line is represented by three numbers separated by a single space: the first number represents a species, the second one represents its value, and the third one represents its weight.
The next line contains one positive integer m = n − 1, which is the number of edges of the input tree. The next m lines contain m edges such that one line contains one edge. Each edge is represented by two positive numbers separated by a single space; the first number represents one end-vertex of the edge, and the second one represents the other end-vertex. Finally, a 0 at the (n + m + 4)th line indicates the end of the first test case.
The next test case starts after the previous ending symbol 0. A-1 singles the end of the whole inputs.
The output contains one line for each test case. Each line contains an integer, which is the density of a weight-constrained maximum-density subtree of the corresponding input tree.
8 1 10000 0 1 0 6 2 10 20 3 0 6 4 1 1 5 3 1 6 2 1 7 10 1 8 5 100 7 1 2 2 3 2 4 4 5 4 6 6 7 6 8 0 6 13 999 1 1 0 100 2 0 100 3 6 6 4 8 8 5 0 100 6 0 100 5 1 3 2 3 3 4 4 5 4 6 -1
10 1
Migrated from old NTUJ.
NCPC2007
| No. | Testdata Range | Score |
|---|