Problems Status Rank Problem 1157 The World Of Dango Time Limit: 2000msMemory 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