#GYM104663E. Fruit Seller of KUETLand
Fruit Seller of KUETLand
Description
In KUETLand there is a strange fruit seller. In his shop, he keeps $n$ different fruits. Each of these fruits has different prices and different nutritional value.
The fruit seller displays his fruits in a unique way. Firstly he takes some ribbons and chooses a particular fruit as the root. Then using the ribbons he ties up all other fruits in a way that creates a tree structure. Now, he hangs up the chosen root fruit with a hook, so that all the fruits get displayed.
Now while selling fruits he always maintains a special condition:
- Each time the customer has to choose a particular fruit. Then the seller cuts down all the ribbons directly tied up with that fruit. As a result, besides the chosen fruit, sometimes some other fruits also get detached from the tree.
In this way, the customer can ask for a fruit multiple times from the available fruit tree, and each time he has to buy all the fruits that will get detached from that currently available tree.
Now there is a little boy in KUETLand, who loves fruits very much. He comes to you with some queries. In each query, he tells you an amount and wants to know what will be the maximum amount of nutrition he can achieve if he buys fruits optimally using this amount.
In the first line there will be an integer $T \; (1 \leq T \leq 10)$ — indicating the number of test cases.
In each test case the first line will contain four integers $n, m, r, q\;(1 \leq n, q \leq 3000, m = n - 1, 1 \leq r \leq n)$ — which indicates the number of fruits, number of fruit edges, the root of the fruit tree and the number of queries respectively.
Then there will be $n$ lines each having two integers representing the price $p\;(1 \leq p \leq 3000)$ and the nutrition value $nv\;(1 \leq nv \leq 3000)$ of that fruit.
Then there will be $m$ lines, each having two integers $a, b\;(1 \leq a, b \leq n, a \neq b)$ describing the tree edges.
Lastly, there will be a line containing $q$ integers $amount_1, \cdots, amount_q\;(1 \leq amount_i \leq 3000)$ describing the query values.
For each test case first you have to print the case number, then there will be $q$ lines answering the queries of that test case.
Input
In the first line there will be an integer $T \; (1 \leq T \leq 10)$ — indicating the number of test cases.
In each test case the first line will contain four integers $n, m, r, q\;(1 \leq n, q \leq 3000, m = n - 1, 1 \leq r \leq n)$ — which indicates the number of fruits, number of fruit edges, the root of the fruit tree and the number of queries respectively.
Then there will be $n$ lines each having two integers representing the price $p\;(1 \leq p \leq 3000)$ and the nutrition value $nv\;(1 \leq nv \leq 3000)$ of that fruit.
Then there will be $m$ lines, each having two integers $a, b\;(1 \leq a, b \leq n, a \neq b)$ describing the tree edges.
Lastly, there will be a line containing $q$ integers $amount_1, \cdots, amount_q\;(1 \leq amount_i \leq 3000)$ describing the query values.
Output
For each test case first you have to print the case number, then there will be $q$ lines answering the queries of that test case.
1
7 6 5 2
4 3
3 8
7 6
5 7
10 7
5 5
6 3
5 6
6 3
1 6
5 2
4 2
7 2
45 19
Case 1:
39
21