[HomeTrainingProblemsContestsC Language]  [LoginRegister] 
Problems Status Rank 
Problem 1157
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 a_{i} dangoes live in hole i (0<=a_{i}<=100000, 1<=i<=N). These holes are connected by N1 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, a_{0}, a_{1},…,a_{N1}, which means the number of dangoes in each hole. Next N1 lines, each line has two integer: a, b(0<=a, b<=N1), 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
