| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank Statistics |
Problem H
The World Of Dango
Time Limit: 2000ms
Memory Limit: 65536kb Description
Maybe you have heard of the WORLD OF DANGO, an interesting game which is popular with girls. But this is a different story. Long long ago, there was a magic kingdom, and many dangoes lives in some holes there. For the sake of simplicity, suppose there are N holes (1<=N<=2000), and ai dangoes live in hole i (0<=ai<=100000, 1<=i<=N). These holes are connected by N-1 undirected tubes. It is guaranteed that all holes are reachable from any one hole through these tubes. There is a greedy cat named Tom. He’s so stupid that he mistakes dangoes as some kind of delicious food! So Tom decided to catch some dangoes and drive back home to cook a big meal. Tom’s car stays at hole S (0 <= S < N) initially. In order to have dinner on time, Tom must finish his work and go back to hole S in P minutes (exclusive), (1<=P<=8000), then drive away. Time would be counted from minute 0. Note that moving from one hole to another hole would cost Tom 1 minute. If Tom wanna catch all the dangoes in the current hole, it would cost him another 2 minutes. Of course to save time, Tom has a choice to give up the dangoes in current hole and move to next hole. Here comes the problem: can you tell Tom the maximum number of dangoes he can catch? 
Input
There are several test cases. For each case:First line contains three integers, N, S, P. Second line contains N integers, a0, a1,…,aN-1, which means the number of dangoes in each hole. Next N-1 lines, each line has two integer: a, b(0<=a, b<=N-1), meaning that there is a tube between hole a and b. Output
A single line for each case, indicating the maximum number of dangoes Tom can catch.
Sample Input
1 0 1 2 1 0 2 2 1 0 100 2 4 0 6 5 5 5 100 0 1 1 3 0 2 Sample Output
0 2 2 100 Source
lianjx@ustc
|